面试题34. 二叉树中和为某一值的路径

题目

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

提示：

节点总数 <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

前序遍历之后，到达叶子节点的时候比较是否相等。
这里采用的是到达一个节点就减掉的策略。

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        self.result = []
        self.travel(root, sum, [])
        return self.result
    def travel(self, root, num, path):
        if root is None : return 
        
        path.append(root.val)
        if root.val == num and not root.left and not root.right: self.result.append(list(path)) 
        if root.left: self.travel(root.left, num-root.val, path)
        if root.right: self.travel(root.right, num-root.val, path)
        # 至关重要
        path.pop()

总结

append到result的时候要list(path)复制一次，不然的话，值还是会跟着变。
最后path要记得pop。
不要试图用值已经比sum大就退出，因为值可能是负数。（坑）