劍指 Offer 34. 二叉樹中和為某一值的路徑

題目介紹

描述：

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

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

              5
             / \\
            4   8
           /   / \\
          11  13  4
         /  \\    / \\
        7    2  5   1
返回:

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

提示：

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

解題思路：

遞歸算法的關(guān)鍵是要明確函數(shù)的「定義」是什么建炫，然后相信這個定義，利用這個定義推導(dǎo)最終結(jié)果辜妓。

寫樹相關(guān)的算法为居，簡單說就是碌宴，先搞清楚當(dāng)前 root 節(jié)點該做什么，然后根據(jù)函數(shù)定義遞歸調(diào)用子節(jié)點颜骤，遞歸調(diào)用會讓孩子節(jié)點做相同的事情唧喉。

二叉樹題目的一個難點在于如何通過題目的要求思考出每一個節(jié)點需要做什么

二叉樹解題策略

一遞歸二隊列 + 迭代（層次遍歷）三棧 + 迭代（非遞歸遍歷）四其它

三種基本的遍歷方式，都可以用遞歸來實現(xiàn)忍抽。寫遞歸算法的時候八孝，需要注意遞歸退出條件以及遞歸操作的表達(dá)。

自己的解法實現(xiàn)

def pathSum4(self, root, sum):
        if not root: return []
        res, stack = [], []

        def getPath(node, _sum):
            stack.append(node.val)
            _sum += node.val
            if _sum == sum and not node.left and not node.right:
                res.append(list(stack))
            if node.left:
                getPath(node.left, _sum)
            if node.right:
                getPath(node.right, _sum)
            stack.pop(-1)

        getPath(root, 0)
        return res

網(wǎng)上比較優(yōu)秀的解法

解法一

解題思路：本問題是典型的二叉樹方案搜索問題鸠项，使用回溯法解決干跛，其包含先序遍歷 + 路徑記錄兩部分。

先序遍歷：按照 “根祟绊、左楼入、右” 的順序，遍歷樹的所有節(jié)點牧抽。路徑記錄：在先序遍歷中嘉熊，記錄從根節(jié)點到當(dāng)前節(jié)點的路徑。當(dāng)路徑為 ① 根節(jié)點到葉節(jié)點形成的路徑且 ② 各節(jié)點值的和等于目標(biāo)值 sum 時扬舒，將此路徑加入結(jié)果列表阐肤。

向上回溯前，需要將當(dāng)前節(jié)點從路徑 path 中刪除讲坎，即執(zhí)行 path.pop() 孕惜。

值得注意的是，記錄路徑時若直接執(zhí)行 res.append(path) 晨炕，則是將 path 對象加入了 res 衫画；后續(xù) path 改變時， res 中的 path 對象也會隨之改變瓮栗。

正確做法：res.append(list(path)) 削罩，相當(dāng)于復(fù)制了一個 path 并加入到 res 。

def pathSum(self, root, sum):
        if not root: return [[]]
        res, path = [], []
        def recur(node, target):
            if not node: return
            path.append(node.val)
            target -= node.val

            if target == 0 and not node.left and not node.right:
                res.append(list(path))
            recur(node.left, target)
            recur(node.right, target)
            path.pop()
        recur(root, sum)
        return res

解法二

使用DFS

def pathSum2(self, root, sum):
        if not root: return [[]]
        res, path = [], []
        def dfs(node, sum):
            # 遞歸出口：解決子問題
            if not node: return    # 如果沒有節(jié)點(node = None)费奸，直接返回鲸郊，不向下執(zhí)行
            else:
                path.append(node.val)    # 將節(jié)點值添加到path
                sum -= node.val
            # 如果節(jié)點為葉子節(jié)點，并且 sum == 0
            if not sum and not node.left and not node.right:
                res.append(path[:])
            dfs(node.left, sum)    # 遞歸處理左邊
            dfs(node.right, sum)   # 遞歸處理右邊
            path.pop()    #處理完一個節(jié)點后货邓，恢復(fù)初始狀態(tài)，為node.left,  node.right操作
        dfs(root, sum)
        return res

解法三

探測二叉樹的每個節(jié)點四濒，沿途記錄路徑列表和累和换况，并判斷：

節(jié)點是葉節(jié)點且累加和剛好滿足要求职辨，則沿途列表加入到結(jié)果列表否則，繼續(xù)對可能的左右子節(jié)點遞歸探測

def pathSum3(self, root, sum):
        if not root: return []
        res = []
        def path(node, sum_, _list):
            if not node.left and not node.right and sum_ == node.val:
                res.append(_list[:] + [node.val])
            if node.left:
                path(node.left, sum_ - node.val, _list + [node.val])
            if node.right:
                path(node.right, sum_ - node.val, _list + [node.val])
        path(root, sum, [])
        return res