考古学家复原古树

# 考古学家复原古树：由前序和中序重建二叉树
from collections import deque

preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def build(pre, ino):
    if not pre:
        return None
    root_val = pre[0]                 # 前序第一个元素一定是根
    k = ino.index(root_val)           # 根在中序里的位置
    root = Node(root_val)
    root.left = build(pre[1:k + 1], ino[:k])      # 中序左边一段是左子树
    root.right = build(pre[k + 1:], ino[k + 1:])  # 中序右边一段是右子树
    return root

def postorder(node, bag):
    if node is None:
        return
    postorder(node.left, bag)
    postorder(node.right, bag)
    bag.append(str(node.val))

root = build(preorder, inorder)

bag = []
postorder(root, bag)
print("前序：" + " ".join(map(str, preorder)))
print("中序：" + " ".join(map(str, inorder)))
print("重建后的后序：" + " ".join(bag))

queue = deque([root])
level = []
while queue:
    node = queue.popleft()
    level.append(str(node.val))
    if node.left is not None:
        queue.append(node.left)
    if node.right is not None:
        queue.append(node.right)
print("重建后的层序：" + " ".join(level))