【Leetcode】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         vector<vector<int>> ret;
14         vector<int> path;
15         //这里注意判断空树，否则需要在下面的函数里面判断
16         if (root != nullptr) {
17             pathSum(root, sum, path, ret);   
18         }
19         return ret;
20     }
21 private:
22     void pathSum(TreeNode *node, int target, vector<int> &path, vector<vector<int>> &ret) {
23         path.push_back(node->val);
24         if (node->left != nullptr) {
25             pathSum(node->left, target - node->val, path, ret);
26         }
27         if (node->right != nullptr) {
28             pathSum(node->right, target - node->val, path, ret);
29         }
30         if (node->left == nullptr && node->right == nullptr) {
31             if(node->val == target) {
32                 ret.push_back(path);
33             }
34         } 
35         path.pop_back();
36     }    
37 };

View Code

递归解决