113_Path Sum II
113. Path Sum II
Level: medium
Tag: tree, dfs
Question
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Example 1
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 1: recursive (w/o defining a helper function)
# 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]]
"""
res = []
if not root:
return res
sum -= root.val
if not root.left and not root.right:
if sum == 0:
res.append([root.val])
if root.left:
for path in self.pathSum(root.left, sum):
res.append([root.val] + path)
if root.right:
for path in self.pathSum(root.right, sum):
res.append([root.val] + path)
return res
Solution 2: iterative (Depth first search, using stack)
# 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 []
res = []
stack = [(root, sum, [])]
while stack:
root, sum, path_list = stack.pop()
sum -= root.val
if not root.left and not root.right:
if sum == 0:
res.append(path_list + [root.val])
if root.right:
stack.append((root.right, sum, path_list + [root.val]))
if root.left:
stack.append((root.left, sum, path_list+ [root.val]))
return res
Last updated