25145: 猜二叉树（按层次遍历）

http://cs101.openjudge.cn/practice/25145/

一棵二叉树，结点都是大写英文字母，且不重复。

给出它的中序遍历序列和后序遍历序列，求其按层次遍历的序列。

输入

第一行是整数n, n <=30，表示有n棵二叉树接下来每两行代表一棵二叉树，第一行是其中序遍历序列，第二行是后序遍历序列

输出

对每棵二叉树输出其按层次遍历序列

样例输入

2
LZGD
LGDZ
BKTVQP
TPQVKB

样例输出

ZLDG
BKVTQP

来源: Guo Wei

python

from collections import deque

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

def build_tree(inorder, postorder):
    if inorder:
        root = Node(postorder.pop())
        root_index = inorder.index(root.data)
        root.right = build_tree(inorder[root_index+1:], postorder)
        root.left = build_tree(inorder[:root_index], postorder)
        return root

def level_order_traversal(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.data)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

n = int(input())
for _ in range(n):
    inorder = list(input().strip())
    postorder = list(input().strip())
    root = build_tree(inorder, postorder)
    print(''.join(level_order_traversal(root)))

25145: 猜二叉树（按层次遍历） ​

25145: 猜二叉树（按层次遍历）