Posted on 2014-01-18 17:49
Uriel 阅读(79)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode
二叉树每个节点有0-9数值，从二叉树根节点到叶节点确定一个整数，求所有这样的整数之和
例如 1
/ \
2 3
sum=12+13=25
BFS，每个队列元素记录从根到该节点为止的整数大小，每次*10+val，遇到叶节点就累加
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 };