LeetCode OJ：Path Sum II（路径和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]
]

求路径的和与某一特定的值时候对等即可，简单的dfs，代码如下：

 1 class Solution {
 2 public:
 3     vector<vector<int>> pathSum(TreeNode* root, int sum) {
 4         vector<int> res;
 5         dfs(root, res, sum);
 6         return ret;
 7     }
 8 
 9     void dfs(TreeNode * root, vector<int> res, int left)
10     {
11         if(!root) return;
12         if(!root->left && !root->right && left == root->val){
13             res.push_back(root->val);
14             ret.push_back(res);
15         }
16         if(left <= root->val)
17             return;
18         else{
19             res.push_back(root->val);
20             if(root->left)
21                 dfs(root->left, res, left -= root->val);
22             if(root->right)
23                 dfs(root->right, res, left -= root->val);
24         }
25     }
26 private:
27     vector<vector<int>> ret;
28 };

java版本代码如下，方法相同，就是java的引用处理起来稍微麻烦点，递归尾部应该pop一下。

 1 public class Solution {
 2     public List<List<Integer>> pathSum(TreeNode root, int sum) {
 3         List<List<Integer>> ret = new ArrayList<List<Integer>>();
 4         Stack<Integer> tmp = new Stack<Integer>();
 5            dfs(ret, tmp, root, sum);
 6            return ret;
 7     }
 8 
 9     public void dfs(List<List<Integer>> ret, Stack<Integer> tmp, TreeNode root, int remain){
10         if(root == null) return;
11         tmp.push(root.val);
12         if(root.left == null && root.right == null)
13             if(remain == root.val)
14                 ret.add((Stack<Integer>)tmp.clone());
15         if(root.left != null) dfs(ret, tmp, root.left, remain - root.val);
16         if(root.right != null) dfs(ret, tmp, root.right, remain - root.val);
17         tmp.pop();
19     }
20 }