Path Sum II
Source
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]
]
Java
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
dfs(root, sum, new ArrayList<Integer>(), result);
return result;
}
public void dfs(TreeNode root, int sum, List<Integer> path, List<List<Integer>> result){
if(root==null) return;
if(root.left==null && root.right==null){
if(sum==root.val){
List<Integer> p = new ArrayList<Integer>(path);
p.add(root.val);
result.add(p);
}
return;
}
path.add(root.val);
dfs(root.left, sum-root.val, path, result);
dfs(root.right, sum-root.val, path, result);
path.remove(path.size()-1);
}
Python
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
result = []
self.dfs(root, sum, [], result)
return result;
def dfs(self, root, sum, path, result):
if root is None:
return;
if root.left is None and root.right is None:
if root.val==sum:
p = path[:]
p.append(sum)
result.append(p)
return
path.append(root.val)
self.dfs(root.left, sum-root.val, path, result)
self.dfs(root.right, sum-root.val, path, result)
path.pop()