Posted on 2014-01-18 17:49
Uriel 閱讀(102)
評論(0) 編輯 收藏 引用 所屬分類:
LeetCode
二叉樹每個節(jié)點有0-9數(shù)值，從二叉樹根節(jié)點到葉節(jié)點確定一個整數(shù)，求所有這樣的整數(shù)之和
例如 1
/ \
2 3
sum=12+13=25
BFS，每個隊列元素記錄從根到該節(jié)點為止的整數(shù)大小，每次*10+val，遇到葉節(jié)點就累加
1 /**
2 * Definition for binary tree
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10 class Solution {
11 public:
12 struct Que {
13 int s;
14 TreeNode *p;
15 }q[100010];
16
17 int sumNumbers(TreeNode *root) {
18 int l = 0, r = 1, res = 0;
19 if(root == NULL) return 0;
20 q[0].p = root;
21 q[0].s = root->val;
22 while(l < r) {
23 if(q[l].p->left == NULL && q[l].p->right == NULL) {
24 res += q[l].s;
25 }
26 if(q[l].p->left != NULL) {
27 q[r].p = q[l].p->left;
28 q[r].s = q[l].s * 10 + q[r].p->val;
29 ++r;
30 }
31 if(q[l].p->right != NULL) {
32 q[r].p = q[l].p->right;
33 q[r].s = q[l].s * 10 + q[r].p->val;
34 ++r;
35 }
36 ++l;
37 }
38 return res;
39 }
40 };