Path Sum II
Problem: Path Sum II
We can do depth-first search on the whole tree and once we get a root-to-leaf path sum to target, we append the path to the results.
Code in Python:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
if not root: return []
ans = []
def dfs(node, _sum, path):
if not node.left and not node.right:
if _sum+node.val == sum: ans.append(path+[node.val])
if node.left: dfs(node.left, _sum+node.val, path+[node.val])
if node.right: dfs(node.right, _sum+node.val, path+[node.val])
dfs(root, 0, [])
return ans