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

創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比西華網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式西華網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋西華地區(qū)。費(fèi)用合理售后完善，10余年實(shí)體公司更值得信賴。

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)髁斜?，可以減少中間的內(nèi)存開銷。
            四個(gè)參數(shù)分別代表了當(dāng)前子樹的先序遍歷和中序遍歷的結(jié)果，根據(jù)這四個(gè)參數(shù)可以從總體的
            先序遍歷和中序遍歷中找到當(dāng)前子樹的先序遍歷和中序遍歷。
            :return: 當(dāng)前子樹的根節(jié)點(diǎn)
            """
            # 對于一棵子樹，其先序遍歷的第一個(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)造二叉樹