Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

[LeetCode]Path Sum [& ||]-2014.01.18

Posted on 2014-01-18 18:06 Uriel 阅读(126) 评论(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 };

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理