重建二叉树

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

解法

    def reConstructBinaryTree(self, preorder, inorder):
        if not preorder or not inorder:
            return None
        if len(preorder) != len(inorder):
            return None

        # 前序第一个为根, 创建根节点
        rootVal = preorder[0]
        rootNode = TreeNode(rootVal)

        # 在中序中找到根对应的索引值，分别划分出：左/右 子树的 前序、中序
        inorderRootPos = inorder.index(rootVal)

        leftSubTreeInorder = inorder[:inorderRootPos]
        rightSubTreeInorder = inorder[inorderRootPos+1:]

        leftSubTreePreorder = preorder[1: inorderRootPos + 1]
        rightSubTreePreorder = preorder[inorderRootPos + 1: ]

        # 分别重建左右子树
        rootNode.left = self.reConstructBinaryTree(leftSubTreePreorder , leftSubTreeInorder)
        rootNode.right= self.reConstructBinaryTree(rightSubTreePreorder , rightSubTreeInorder)

        return rootNode