[leetCode]Path Sum&&Path Sum II

Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / 
            4   8
           /   / 
          11  13  4
         /        
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Path Sum很好做，只要递归时sum为0则返回true就好了。

 1 #include <iostream>
 2 #include <vector>
 3 #include <stack>
 4 using namespace std;
 5 
 6 struct TreeNode {
 7     int val;
 8     TreeNode *left;
 9     TreeNode *right;
10     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
11 };
12 class Solution {
13 public:
14     bool hasPathSum(TreeNode *root, int sum) {
15         if(root == NULL) return false;
16         sum = sum - root->val;
17         bool isThisPath = false;
18         if(root->left != NULL)    isThisPath = hasPathSum(root->left,sum);
19         if(isThisPath)    return true;
20         if(root->right != NULL) isThisPath = hasPathSum(root->right,sum);
21         if(isThisPath)    return true;
22         if(root->left == NULL && root->right == NULL && sum == 0) return true;
23         if(root->left == NULL && root->right == NULL && sum != 0) return false;
24         return isThisPath;
25     }
26 }

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / 
            4   8
           /   / 
          11  13  4
         /      / 
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

Path SumII 做的稍微久一点，一开始递归没想清楚。

Path SumII是找从根节点到叶结点的节点中有多少条分支的和可以为一个确定值的问题，输出是路径的集合。

用递归来思考的话还是很简单的，每个节点只要确定他的孩子节点是不是在路径上（即孩子节点是不是在和为定值sum的路径上），如果是，则把自己加入，如果不是，则不加入。

递归的结束条件则是如果节点为叶子节点，且sum在此时为0.

这个基础上，两种解法：

解法一是自顶向下，如果父节点发现本身是在和为定值的路径上（使用Path SumI的结果），则将自己加入路径节点中，然后遍历自己的子节点，依次循环，最后在叶结点中将整条路径加入路径的集合中。

解法一代码：

 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     vector<vector<int> > retvv;
13     bool hasPathSum(TreeNode *root, int sum) {
14         if(root == NULL) return false;
15         sum = sum - root->val;
16         bool isThisPath = false;
17         if(root->left != NULL)    isThisPath = hasPathSum(root->left,sum);
18         if(isThisPath)    return true;
19         if(root->right != NULL) isThisPath = hasPathSum(root->right,sum);
20         if(isThisPath)    return true;
21         if(root->left == NULL && root->right == NULL && sum == 0) return true;
22         if(root->left == NULL && root->right == NULL && sum != 0) return false;
23         return isThisPath;
24     }
25     vector<vector<int> > pathSum(TreeNode *root, int sum){
26         vector<int> path;
27         if(root== NULL)    return retvv;
28         return onePath(root,sum,path);
29     } 
30     vector<vector<int> > onePath(TreeNode *root, int sum, vector<int> path){
31         if(root == NULL)    path.clear(); 
32         int cursum = sum - root->val;
33         if(root->left == NULL && root->right == NULL && cursum == 0){
34             path.push_back(root->val);
35             retvv.push_back(path);
36             return retvv;
37         }
38         if(root->left == NULL && root->right == NULL && cursum != 0){
39             return retvv;
40         }
41         if(hasPathSum(root,sum)) {
42             path.push_back(root->val);
43             if(hasPathSum(root->left,cursum)) 
44                 onePath(root->left,cursum,path);
45             if(hasPathSum(root->right,cursum)) 
46                 onePath(root->right,cursum,path);
47         }
48         return retvv;
49     }
50 };

解法二是自下向上，每次先确定其孩子节点在不在路径中，如果孩子节点在，则把自己加入路径中。

解法二代码：

 1 #include <iostream>
 2 #include <vector>
 3 #include <stack>
 4 using namespace std;
 5 
 6 struct TreeNode {
 7     int val;
 8     TreeNode *left;
 9     TreeNode *right;
10     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
11 };
12 class Solution {
13 public:
14     vector<vector<int> > retvv;
15     vector<vector<int> > pathSum(TreeNode *root, int sum) {    
16         if(root == NULL)    return retvv;
17         sum = sum - root->val;
18         if(root->left == NULL && root->right == NULL && sum == 0){
19             vector<int> vec;
20             vec.push_back(root->val);
21             retvv.push_back(vec);
22             return retvv;
23         }
24         if(root->left == NULL && root->right == NULL && sum != 0){
25             return retvv;
26         }
27         size_t preSize = retvv.size();
28         if(root->left != NULL) pathSum(root->left,sum);
29         if(root->right != NULL) pathSum(root->right,sum);
30         for(preSize; preSize < retvv.size();preSize++){
31             retvv[preSize].insert(retvv[preSize].begin(),root->val);
32         }
33         return retvv;
34     }
35 };

实测解法一代码虽然长一些，但是运行速度比解法二快两倍多(320/840)。猜测应该是在vector中使用insert函数导致的。

艰难的成长