剑指offer：重建二叉树

题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

创新互联-专业网站定制、快速模板网站建设、高性价比西华网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式西华网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖西华地区。费用合理售后完善，10余年实体公司更值得信赖。

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)  # 递归构造二叉树