原题
给定一个二叉树，找出所有路径中各节点相加总和等于给定 目标值
的路径。
一个有效的路径，指的是从根节点到叶节点的路径。
给定一个二叉树，和目标值 = 5
1
/ \
2 4
/ \
2 3
返回
[
[1, 2, 2],
[1, 4]
]
解题思路
- DFS - 递归求解
- 类似于求subset的思路，维护一个path，从根节点向下分别沿左右子树搜索。在确保当前节点不为空的情况下，求剩余值
remaining = target - root.val - 如果剩余值为0 - 把当前的path加入到result中
- 如果剩余值不为0 - 继续向下朝左右子树寻找，target传入remaining的值
- 注意每次path要加入root.val，但是每次返回上一层要pop出去刚刚加入的值，或者换一种方式
else:
self.helper(root.left, remaining, result, path+[root.val])
self.helper(root.right, remaining, result, path+[root.val])
完整代码
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
# @param {TreeNode} root the root of binary tree
# @param {int} target an integer
# @return {int[][]} all valid paths
def binaryTreePathSum(self, root, target):
# Write your code here
res = []
self.helper(root, target, res, [])
return res
def helper(self, root, target, result, path):
if root:
remaining = target - root.val
if remaining == 0:
result.append(path+[root.val])
else:
path.append(root.val)
self.helper(root.left, remaining, result, path)
self.helper(root.right, remaining, result, path)
path.pop()
