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] ]Solution:O(n)
public class Solution { public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) { ArrayList<ArrayList<Integer>> list = new ArrayList<>(); if(root == null) return list; if(root.left == null && root.right == null){ if(root.val == sum){ ArrayList<Integer> s = new ArrayList<>(); s.add(sum); list.add(s); return list; }
}
if(root.left !=null){
for(ArrayList<Integer> s: pathSum(root.left, sum-root.val)){
s.add(0,root.val); list.add(s); } } if(root.right !=null){ for(ArrayList<Integer> s:pathSum(root.right, sum-root.val)){ s.add(0,root.val);
list.add(s); } } return list; } }
沒有留言:
張貼留言