# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
def copyAndAppd(oldList, ele):
newList = [each for each in oldList]
newList.append(ele)
return newList
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
self.pathList = []
self.curList = []
self.findPath(root, sum)
return self.pathList
def findPath(self, root, sum):
if root == None:
return
if root.right == None and root.left == None and root.val == sum:
self.pathList.append(copyAndAppd(self.curList, root.val))
self.curList.append(root.val)
self.findPath(root.left, sum-root.val)
self.findPath(root.right, sum-root.val)
del self.curList[-1]
https://leetcode.com/problems/path-sum-ii/#/description
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]
]