6/22/2017 - 7:58 AM

## 113. Path Sum II

1. Path Sum II
``````# 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]
]
``````