原题
给出一个二叉树和一个sum, 找出所有存在的自根节点到叶节点的路径，如果路径和等于sum
样例
给出如下二叉树和 sum = 22
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回
[
[5,4,11,2],
[5,8,4,5]
]
解题思路
- 二叉树遍历
- helper函数要保存subSum, path，当节点为根节点而且和等于sum时，向res中添加此刻的path
完整代码
# 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
self.helper(root, [], 0, sum, res)
return res
def helper(self, root, path, subSum, sum, res):
if root.left == None and root.right == None:
if subSum + root.val == sum:
res.append(path + [root.val])
if root.left:
self.helper(root.left, path + [root.val], subSum + root.val, sum, res)
if root.right:
self.helper(root.right, path + [root.val], subSum + root.val, sum, res)
