題目描述
輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。

正陽ssl適用于網站、小程序/APP、API接口等需要進行數(shù)據傳輸應用場景，ssl證書未來市場廣闊！成為成都創(chuàng)新互聯(lián)的ssl證書銷售渠道，可以享受市場價格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：13518219792（備注：SSL證書合作）期待與您的合作！

class Solution:
    # 返回構造的TreeNode根節(jié)點
    def reConstructBinaryTree(self, preorder, inorder):
        """
        與樹有關的題目一般來講可以先嘗試使用遞歸方法求解。
        :param preorder: 一棵樹的先序遍歷結果
        :param inorder: 同一棵樹的中序遍歷結果
        :return: 構造的樹的根節(jié)點
        """
        def helper(preorder_start, preorder_end, inorder_start, inorder_end):
            """
            通過傳下標代替?zhèn)髁斜恚梢詼p少中間的內存開銷。
            四個參數(shù)分別代表了當前子樹的先序遍歷和中序遍歷的結果，根據這四個參數(shù)可以從總體的
            先序遍歷和中序遍歷中找到當前子樹的先序遍歷和中序遍歷。
            :return: 當前子樹的根節(jié)點
            """
            # 對于一棵子樹，其先序遍歷的第一個節(jié)點就是根節(jié)點
            root = TreeNode(preorder[preorder_start])
            # 如果當前子樹只有一個節(jié)點(這時這個子樹其實是葉子節(jié)點)，這是我們的遞歸出口
            if preorder_start == preorder_end:
                # 這里增加了一個輸入合法性判斷
                if inorder_start == inorder_end \
                        and preorder[preorder_end] == inorder[inorder_end]:
                    return root
                else:
                    return None

            # 然后從中序遍歷中找到這個根節(jié)點，按照中序遍歷的順序，根節(jié)點左邊的是左子樹的節(jié)點，
            # 右邊的是右子樹的節(jié)點
            i = inorder_start
            while i <= inorder_end:
                if inorder[i] == root.val:
                    break
                i += 1

            # 輸入合法性判斷，確保這個根節(jié)點在中序遍歷中能找到
            if inorder[i] != root.val:
                return None

            left_length = i - inorder_start  # 左子樹的節(jié)點數(shù)
            # 左右子樹的先序遍歷下標
            preorder_left_start = preorder_start + 1
            preorder_left_end = preorder_left_start + left_length - 1
            preorder_right_start = preorder_left_end + 1
            preorder_right_end = preorder_end

            # 左右子樹的中序遍歷的下標
            inorder_left_start = inorder_start
            inorder_left_end = i - 1
            inorder_right_start = i + 1
            inorder_right_end = inorder_end

            # 如果存在左右子樹，則遞歸下去
            if left_length > 0:
                root.left = helper(preorder_left_start, preorder_left_end,
                                   inorder_left_start, inorder_left_end)
            if left_length < preorder_end - preorder_start:
                root.right = helper(preorder_right_start, preorder_right_end,
                                    inorder_right_start, inorder_right_end)

            return root

        if not preorder or not inorder:  # 驗證輸入合法性
            return None

        return helper(0, len(preorder) - 1, 0, len(inorder) - 1)  # 遞歸構造二叉樹

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

本文標題：劍指offer：重建二叉樹-創(chuàng)新互聯(lián)
文章網址：http://aaarwkj.com/article24/dopgce.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供網站改版、定制開發(fā)、網站策劃、域名注冊、網站設計公司、微信公眾號

廣告

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