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

創(chuàng)新互聯(lián)2013年開(kāi)創(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ù)解決您的所有建站問(wèn)題。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

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

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

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

            # 在訪問(wèn)完這個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)之后會(huì)返回到其父節(jié)點(diǎn)中，
            # 在返回之前應(yīng)該在路徑中刪除這個(gè)節(jié)點(diǎn)
            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元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

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

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

廣告

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