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