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

# 说明：前序，后序，中序，都是指的根节点的位置，前：根左右，中：左根右，后：左右根
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# 根本思想是找到这棵树的根节点root，就算完成了
def  re_order(pre,middle):
    if len(pre)==0:
        return None
    if len(pre)==1:
        return pre[0]
    root = pre[0]
    # 左右子树的中序遍历
    treeMIDL = middle[:middle.index(pre[0])]
    treeMIDR = middle[middle.index(pre[0])+1:]
    # 左右子树的前序遍历
    treePreL = pre[1:middle.index(pre[0])+1]
    treePreR = pre[middle.index(pre[0])+1:]

    root.left=re_order(treePreL,treeMIDL)
    root.right=re_order(treePreR,treeMIDR)
    return root

# 测试方法，验证最后再按照前序遍历打印，能不能得出一样的结果
def print_root(root1):
    if root1==None:
        return
    print(root1.val)
    print_root(root1.left)
    print_root(root1.right)

Node1 = TreeNode(1)
Node2 = TreeNode(2)
Node3 = TreeNode(3)
Node4 = TreeNode(4)
Node5 = TreeNode(5)
Node6 = TreeNode(6)
Node7 = TreeNode(7)
Node8 = TreeNode(8)

my_pre = [Node1,Node2,Node4,Node7,Node3,Node5,Node6,Node8]
my_mid = [Node4,Node7,Node2,Node1,Node5,Node3,Node8,Node6]

my_root = re_order(my_pre,my_mid)

print_root(my_root)