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
     
      
       > pathSum(TreeNode* root, int sum) { 4         vector
       
         res; 5         dfs(root, res, sum); 6         return ret; 7     } 8  9     void dfs(TreeNode * root, vector
        
          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
         
          
           > ret;28 };
          
         
        
       
      
     

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

1 public class Solution { 2     public List
     
      
       > pathSum(TreeNode root, int sum) { 3         List
       
        
         > ret = new ArrayList
         
          
           >(); 4 Stack
           
             tmp = new Stack
            
             (); 5 dfs(ret, tmp, root, sum); 6 return ret; 7 } 8 9 public void dfs(List
             
              
               > ret, Stack
               
                 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
                
                 )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 }