題目

輸入一棵二叉樹和一個(gè)整數(shù)，打印出二叉樹中節(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。從樹的根節(jié)點(diǎn)開始往下一直到葉節(jié)點(diǎn)所經(jīng)過的節(jié)點(diǎn)形成一條路徑。

示例:
給定如下二叉樹，以及目標(biāo)和 sum = 22，

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

返回:

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

提示：

節(jié)點(diǎn)總數(shù) <= 10000

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解法

前序遍歷之后，到達(dá)葉子節(jié)點(diǎn)的時(shí)候比較是否相等。
這里采用的是到達(dá)一個(gè)節(jié)點(diǎn)就減掉的策略。

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)
        # 至關(guān)重要
        path.pop()

總結(jié)

append到result的時(shí)候要list(path)復(fù)制一次，不然的話，值還是會(huì)跟著變。
最后path要記得pop。
不要試圖用值已經(jīng)比sum大就退出，因?yàn)橹悼赡苁秦?fù)數(shù)。（坑）