面试题7：重建二叉树

【题目描述】
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
【思路】
前序遍历中第一个数为根节点，在中序遍历中寻找到根节点之后，可区分左右子树，便可递归构建左右子树
注意边界条件判断
1.若前序、中序为空，则二叉树为NULL
2.递归时，若只剩一个节点，则该节点即为根节点，退出递归调用。
【代码】

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        def ConstructBinaryNode(pre,tin):
            tinlen = len(tin)
            rootvalue = pre[0]
            root = TreeNode(rootvalue)
            if tinlen==1:
                return root
            
            #在中序遍历中寻找根节点
            leftlength = 0
            while leftlength<tinlen and tin[leftlength]!=rootvalue:
                leftlength+=1
            #构建左子树
            if leftlength>0:
                root.left = ConstructBinaryNode(pre[1:leftlength+1],tin[0:leftlength])
            #构建右子树
            if tinlen-leftlength>=2:
                root.right = ConstructBinaryNode(pre[leftlength+1:],tin[leftlength+1:])
            return root
        prelen = len(pre)
        tinlen = len(tin)
        #树为空判断
        if prelen==0 or tinlen==0:
            return NULL
        return ConstructBinaryNode(pre,tin)