原题

给定一个二叉树，找出所有路径中各节点相加总和等于给定 目标值
的路径。
一个有效的路径，指的是从根节点到叶节点的路径。

给定一个二叉树，和目标值 = 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()