首页 > 代码库 > Leetcode | Path Sum I && II

Leetcode | Path Sum I && II

2024-07-03 18:08:26   229人阅读

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 };

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 };


联系
我们