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

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

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

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

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

            left_length = i - inorder_start  # 左子樹的節(jié)點(diǎn)數(shù)
            # 左右子樹的先序遍歷下標(biāo)
            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

            # 左右子樹的中序遍歷的下標(biāo)
            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:  # 驗(yàn)證輸入合法性
            return None

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

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

文章題目：劍指offer：重建二叉樹-創(chuàng)新互聯(lián)
標(biāo)題鏈接：http://weahome.cn/article/dopgce.html