劍指offer：二叉樹中和為某一值的路徑-創(chuàng)新互聯(lián)

題目描述
輸入一顆二叉樹的跟節(jié)點和一個整數(shù)，打印出二叉樹中結(jié)點值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點開始往下一直到葉結(jié)點所經(jīng)過的結(jié)點形成一條路徑。(注意: 在返回值的list中，數(shù)組長度大的數(shù)組靠前)

創(chuàng)新互聯(lián)2013年開創(chuàng)至今，先為鎮(zhèn)海等服務(wù)建站，鎮(zhèn)海等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為鎮(zhèn)海企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    # 返回二維列表，內(nèi)部每個列表表示找到的路徑
    """
    根據(jù)題目定義，一個路徑總是從根節(jié)點開始的，而搜索路徑本質(zhì)上又和樹的遍歷有關(guān)，那么我們可以思考常
    用的樹的遍歷中哪種遍歷方法可能有效，在這里答案就是先序遍歷，因為先序遍歷也是從根節(jié)點開始的。
    由于題目要求搜索所有可能的路徑，一個路徑在一層里面只經(jīng)過一個節(jié)點，那么就是深度優(yōu)先搜索DFS。

    具體到路徑的定義，需要從根節(jié)點到葉節(jié)點，因此每遍歷到一個節(jié)點的時候，如果這個節(jié)點是葉節(jié)點，那么
    我們就應(yīng)該判斷當(dāng)前的路徑是否符合要求，而如果這個節(jié)點不是葉節(jié)點，那么就選擇一個子節(jié)點繼續(xù)遍歷。
    當(dāng)一個節(jié)點的所有子節(jié)點都已經(jīng)訪問完畢之后，由于遞歸的特性會自動返回到其父節(jié)點，因此我們需要手動
    從路徑中刪除這個節(jié)點
    """
    def FindPath(self, root, expectNumber):
        def helper(cur_root, path):
            # 遍歷到一個節(jié)點的時候先將其加入路徑中
            path.append(cur_root.val)
            # 如果這個節(jié)點是葉節(jié)點，那么判斷當(dāng)前路徑是否符合要求
            if not cur_root.left and not cur_root.right:
                if sum(path) == expectNumber:
                    # 這里注意不能res.append(path)，因為path只是一個id，綁定了內(nèi)存中的
                    # 一個列表，而我們后面還會修改這個列表，因此需要將當(dāng)前路徑的一個拷貝加到
                    # 返回結(jié)果當(dāng)中
                    res.append(path[:])

            # 如果當(dāng)前節(jié)點不是葉節(jié)點，那么訪問其子節(jié)點
            if cur_root.left:
                helper(cur_root.left, path)
            if cur_root.right:
                helper(cur_root.right, path)

            # 在訪問完這個節(jié)點的所有子節(jié)點之后會返回到其父節(jié)點中，
            # 在返回之前應(yīng)該在路徑中刪除這個節(jié)點
            path.pop(-1)

        if not root:
            return []

        res = []
        helper(root, [])
        return res

def main():
    root = TreeNode(10)
    root.left = TreeNode(5)
    root.right = TreeNode(12)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(7)

    solution = Solution()
    print(solution.FindPath(root, 22))

if __name__ == '__main__':
    main()

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)cdcxhl.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

分享名稱：劍指offer：二叉樹中和為某一值的路徑-創(chuàng)新互聯(lián)
瀏覽路徑：http://muchs.cn/article28/hgejp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供Google、網(wǎng)站導(dǎo)航、定制網(wǎng)站、軟件開發(fā)、面包屑導(dǎo)航、網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

小程序開發(fā)