Posted on 2014-01-18 18:06
Uriel 閱讀(145)
評論(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 };