Most of you already know me, please be brutal, and treat this code as if it was written at a top tech interview company.
Question:
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] ]
Time taken: 26 minutes (all 110 test cases passed)
Worst case: \$O(n^2)\$?
Since when I add to resList, it copies all the elements again which can take \$O(n)\$ and I traverse \$O(n)\$ nodes.
Space complexity: \$O(n)\$
My code:
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> curList = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
if(root==null){
return res;
}
curList.add(root.val);
if(root.left==null && root.right==null){
if(sum - root.val==0){
res.add(new ArrayList<Integer>(curList));
}
}
if(root.left!=null){
pathSum(root.left, sum-root.val);
}
if(root.right!=null){
pathSum(root.right, sum-root.val);
}
curList.remove(new Integer(root.val));
return res;
}