Leetcode | Path Sum I && II

Path Sum I

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.

递归求解就可以。注意叶子结点条件是左右结点都为空。

 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     bool hasPathSum(TreeNode *root, int sum) {
13         if (root == NULL) return false;
14         return recursive(root, sum, 0);
15     }
16     
17     bool recursive(TreeNode *root, int sum, int cur) {
18         if (root == NULL) {
19             return false;
20         }
21         
22         cur += root->val;
23         
24         // leaf
25         if (root->left == NULL && root->right == NULL) {
26             return cur == sum;
27         }
28         
29         bool res = recursive(root->left, sum, cur);
30         if (res) return true;
31         return recursive(root->right, sum, cur);
32     }
33 };

第三次刷写得简洁许多，我今天已经重复了好多次这一句了。。。

 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     bool hasPathSum(TreeNode *root, int sum) {
13         if (root == NULL) return false;
14         sum -= root->val;
15         if (root->left == NULL && root->right == NULL && sum == 0) return true;
16         return (hasPathSum(root->left, sum) || hasPathSum(root->right, sum));
17     }
18 };

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]
]

 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> > pathSum(TreeNode *root, int sum) {
13         if (root == NULL) return ret;
14         vector<int> v;
15         
16         int curSum = 0;
17         recursive(root, sum, curSum, v);
18         return ret;
19     }
20     
21     void recursive(TreeNode *root, int sum, int curSum, vector<int> &v) {
22         if (root == NULL) return;
23         
24         curSum += root->val;
25         v.push_back(root->val);
26         if (root->left == NULL && root->right == NULL) {
27             if (curSum == sum) {
28                 ret.push_back(v);
29             }
30         }
31         recursive(root->left, sum, curSum, v);
32         recursive(root->right, sum, curSum, v);
33         v.pop_back();
34     }
35 
36 private:
37     vector<vector<int> > ret;
38 };

第三次。

 1 class Solution {
 2 public:
 3     void recurse(TreeNode *root, int sum, vector<int> &temp, vector<vector<int> > &ans) {
 4         if (root == NULL) return;
 5         sum -= root->val;
 6         temp.push_back(root->val);
 7         if (root->left == NULL && root->right == NULL && sum == 0) {
 8             ans.push_back(temp);
 9         } else {
10             recurse(root->left, sum, temp, ans);
11             recurse(root->right, sum, temp, ans);
12         }
13         temp.pop_back();
14     }
15     vector<vector<int> > pathSum(TreeNode *root, int sum) {
16         vector<vector<int> > ans;
17         vector<int> temp;
18         recurse(root, sum, temp, ans);
19         return ans;
20     }
21 };