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:
Recursive DFS
Base case/ terminating case:
current node is leaf node: if sum==target, add the sum to path and add the path to result list otherwise do nothing.
Recursion steps:
Try current node: if current.left is not null, recursively check its left subtree, when backtrack to current node, recursively check its right subtree, if cur.right is not null as well.
Recursive DFS
Base case/ terminating case:
current node is leaf node: if sum==target, add the sum to path and add the path to result list otherwise do nothing.
Recursion steps:
Try current node: if current.left is not null, recursively check its left subtree, when backtrack to current node, recursively check its right subtree, if cur.right is not null as well.
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res=new ArrayList<List<Integer>>();
List<Integer> paths=new ArrayList<Integer>();
helper(res,paths,root,sum);
return res;
}
public void helper(List<List<Integer>> res, List<Integer> paths,TreeNode root, int sum){
if(root==null) return;
if(root.left==null && root.right==null && sum==root.val){
List<Integer> temp=new ArrayList<Integer>(paths);
temp.add(sum);
res.add(temp);
return;
}
if(root.left!=null){
paths.add(root.val);
helper(res,paths,root.left, sum-root.val);
paths.remove(paths.size()-1);
}
if(root.right!=null){
paths.add(root.val);
helper(res,paths,root.right,sum-root.val);
paths.remove(paths.size()-1);
}
}
No comments:
Post a Comment