Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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]
- ]
- # 1.
- # 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 []
- if not root.left and not root.right and sum == root.val:
- return [[root.val]]
- tmp = self.pathSum(root.left, sum-root.val) + self.pathSum(root.right, sum-root.val)
- return [[root.val]+i for i in tmp]
- #2.
- def pathSum(self, root, sum):
- """
- :type root: TreeNode
- :type sum: int
- :rtype: List[List[int]]
- """
- if not root:
- return []
- pl = []
- self.path(root, sum, [], pl)
- return pl
- def path(self, root, sum, onePath, pl):
- if not root.left and not root.right and root.val == sum:
- onePath.append(root.val)
- pl.append(onePath)
- if root.left:
- self.path(root.left, sum-root.val, onePath+[root.val],pl)
- if root.right:
- self.path(root.right, sum-root.val, onePath+[root.val],pl)
Add Comment
Please, Sign In to add comment