劍指offer：重建二叉樹

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

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

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

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

            left_length = i - inorder_start  # 左子樹的節點數
            # 左右子樹的先序遍歷下標
            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)  # 遞歸構造二叉樹