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枚举。

class Solution {    public List
     
      
       > pathSum(TreeNode root, int sum) {        List
       
        
         > result = new ArrayList<>();        List
         
           tmp = new ArrayList<>();                pathSumHelper(root,tmp,result,sum);                return result;            }        private void pathSumHelper(TreeNode root, List
          
            tmp, List
           
            
             > result, int sum){ if(root == null) return; if(root.left==null && root.right==null && root.val == sum){ tmp.add(root.val); result.add(new ArrayList
             
              (tmp)); tmp.remove(tmp.size()-1); return; } tmp.add(root.val); pathSumHelper(root.left,tmp,result,sum-root.val); pathSumHelper(root.right,tmp,result,sum-root.val); tmp.remove(tmp.size()-1); } }
             
            
           
          
         
        
       
      
     

 

 

 第三遍记录：最好采用第二遍的方法，在叶子节点的时候就判断是否满足条件，但是注意此时该节点并未加入到tmp中去，所以需要tmp中先加入root.val，然后 res中添加tmp，最后tmo中的root.val要删掉。

如果在叶子节点的子节点，null节点判断（此时判断n==0即可），但是左右null节点都会满足条件而产生两边结果。

以下方法会有重复元素

import java.util.ArrayList;import java.util.List;public class Solution {    public List
     
      
       > pathSum(TreeNode root, int sum) {        List
       
        
         > res = new ArrayList
         
          
           >(); if (root == null) return res; List
           
             tmp = new ArrayList
            
             (); pathSumHelper(root, sum, res, tmp); return res; } private void pathSumHelper(TreeNode root, int sum, List
             
              
               > res, List
               
                 tmp) { if (root == null) { if (sum == 0) res.add(new ArrayList
                
                 (tmp)); return; } tmp.add(root.val); pathSumHelper(root.left, sum - root.val, res, tmp); pathSumHelper(root.right, sum - root.val, res, tmp); tmp.remove(tmp.size() - 1); } public static void main(String[] args) { TreeNode root = new TreeNode(5); root.left = new TreeNode(4); root.left.left = new TreeNode(11); root.right = new TreeNode(8); root.right.right = new TreeNode(7); System.out.println(new Solution().pathSum(root, 20)); }}