Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
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]
]
There is one thing need to notice, at line 23, we divided it into 2 sub-tree, so in case left currPath
influence right currPath
, I make a hard copy of it.
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
self.ans = []
self.totalSum = sum
self.pathSumHelper(root, 0, [])
return self.ans
def pathSumHelper(self, node, currSum, currPath):
if not node:
return False
currSum += node.val
currPath.append(node.val)
if not node.left and not node.right and currSum == self.totalSum:
self.ans.append(currPath)
else:
self.pathSumHelper(node.left, currSum, currPath[:]) # to avoid influence right path
self.pathSumHelper(node.right, currSum, currPath)