Posted on 2014-01-18 18:06
Uriel 阅读(128)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode
Path Sum
给一棵二叉树和一个整数，二叉树中每个节点有个权值，每条从根节点到叶节点的路权值求和，问是否存在权值和等于给定数的
BFS，记录权值和，到叶节点的时候判断是否等于给定的数
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 bool hasPathSum(TreeNode *root, int sum) {
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 if(q[l].s == sum) return true;
25 }
26 if(q[l].p->left != NULL) {
27 q[r].p = q[l].p->left;
28 q[r].s = q[l].s + 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 + q[r].p->val;
34 ++r;
35 }
36 ++l;
37 }
38 return false;
39 }
40 };
Path Sum II
上一题的加强版，要输出所有权值和等于给定整数的路径，开个变量记录队列元素之前一个遍历的节点，到叶子节点时若权值和等于给定数，则递归找出路径
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, fa;
14 TreeNode *p;
15 }q[100010];
16
17 vector<vector<int> > pathSum(TreeNode *root, int sum) {
18 int l = 0, r = 1;
19 vector<vector<int> > res;
20 res.clear();
21 if(root == NULL) return res;
22 q[0].p = root;
23 q[0].fa = -1;
24 q[0].s = root->val;
25 while(l < r) {
26 if(q[l].p->left == NULL && q[l].p->right == NULL) {
27 if(q[l].s == sum) {
28 vector<int> t;
29 int tp = l;
30 while(tp >= 0) {
31 t.push_back(q[tp].p->val);
32 tp = q[tp].fa;
33 }
34 reverse(t.begin(), t.end());
35 res.push_back(t);
36 }
37 }
38 if(q[l].p->left != NULL) {
39 q[r].p = q[l].p->left;
40 q[r].fa = l;
41 q[r].s = q[l].s + q[r].p->val;
42 ++r;
43 }
44 if(q[l].p->right != NULL) {
45 q[r].p = q[l].p->right;
46 q[r].fa = l;
47 q[r].s = q[l].s + q[r].p->val;
48 ++r;
49 }
50 ++l;
51 }
52 return res;
53 }
54 };