二叉树的路径和

 1 /**
 2  * Definition of TreeNode:
 3  * class TreeNode {
 4  * public:
 5  *     int val;
 6  *     TreeNode *left, *right;
 7  *     TreeNode(int val) {
 8  *         this->val = val;
 9  *         this->left = this->right = NULL;
10  *     }
11  * }
12  */
13 class Solution {
14 public:
15     /**
16      * @param root the root of binary tree
17      * @param target an integer
18      * @return all valid paths
19      */
20     vector<vector<int>> binaryTreePathSum(TreeNode *root, int target) {
21         vector<vector<int>> res;
22         helper(root, target, vector<int>(), res);
23         return res;
24     }
25     
26     void helper(TreeNode *root, int target, vector<int> cur, vector<vector<int>> & res) {
27         if (root == NULL) {
28             return;
29         }
30         
31         cur.push_back(root->val);
32         helper(root->left, target - root->val, cur, res);
33         helper(root->right, target - root->val, cur, res);
34         
35         if (target - root->val == 0) {
36             res.push_back(cur);
37         }
38     }
39 };

 1 /**
 2  * Definition of TreeNode:
 3  * class TreeNode {
 4  * public:
 5  *     int val;
 6  *     TreeNode *left, *right;
 7  *     TreeNode(int val) {
 8  *         this->val = val;
 9  *         this->left = this->right = NULL;
10  *     }
11  * }
12  */
13 class Solution {
14 public:
15     /**
16      * @param root the root of binary tree
17      * @param target an integer
18      * @return all valid paths
19      */
20     vector<vector<int>> binaryTreePathSum(TreeNode *root, int target) {
21         if (root == NULL) {
22             return vector<vector<int>>();
23         }
24         
25         if (root->val == target && root->left == NULL && root->right == NULL) {
26             return vector<vector<int>>(1, vector<int>(1, target));
27         }
28         
29         vector<vector<int>> left = binaryTreePathSum(root->left, target - root->val);
30         vector<vector<int>> right = binaryTreePathSum(root->right, target - root->val);
31         
32         left.insert(left.end(), right.begin(), right.end());
33         for (int i = 0; i < left.size(); i ++) {
34             left[i].insert(left[i].begin(), root->val);
35         }
36         
37         return left;
38     }
39 };