Leetcode 113: path sum II

link

subject ：

Ideas ：dfs

The idea is similar to change , Every time you recurse down , Add up the number you want sum Subtract the current node root Of val, In this way, we can get the money we need to collect from the next layer , Until the leaf node sum Equal to node will path Add to r ！

Because you want to add nodes all the way from the root node to path, So it's preorder traversal ;

To get multiple paths , Use similar permutations ：① choice ② recursive ③ withdraw
When choosing , Meeting the conditions will path Add to r, Recall after traversal , Maintain a path The sum used to store paths ;

class Solution {
    
    List<List<Integer>> r=new LinkedList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
    
        dfs(root,sum);
        return r;
    }

    void dfs(TreeNode root,int sum){
    
        if(root==null){
    
            return;
        }
        //  choice 
        path.add(root.val);
            //  If it is a leaf node and meets sum Just add ！
        if(root.left==null && root.right==null && sum==root.val){
    
            r.add(new LinkedList(path));
        }

        //  recursive 
        dfs(root.left,sum-root.val);
        dfs(root.right,sum-root.val);
        
        //  withdraw 
        path.removeLast();
    }

}