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]
]

One submission to pass. Yaay!

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> result = new LinkedList<List<Integer>>(); List<Integer> path = new LinkedList<Integer>(); dfs(root,result,path,0,sum); return result; } void dfs(TreeNode root,List<List<Integer>> result, List<Integer> path,int curSum,int sum){ if(root==null)return; curSum+=root.val; path.add(root.val); //at leaf node, decide if new list should be created according to sum matching if(root.left==null&&root.right==null&&curSum==sum){ LinkedList<Integer> aList= new LinkedList<Integer>(); aList.addAll(path); result.add(aList); path.clear(); return; } //left List<Integer> newList = new LinkedList<Integer>(); newList.addAll(path);//use a different list to reserve same path for right dfs(root.left,result,newList,curSum,sum); newList.clear(); newList.addAll(path); dfs(root.right,result,newList,curSum,sum); } }