2024年华为OD机试真题-二叉树的广度优先遍历-Python-OD统一考试（C卷）

题目描述：

有一棵二叉树，每个节点由一个大写字母标识(最多26个节点）。现有两组字母，分别表示后序遍历（左孩子->右孩子->父节点）和中序遍历（左孩子->父节点->右孩子）的结果，请输出层次遍历的结果。

输入描述：

输入为两个字符串，分别是二叉树的后续遍历和中序遍历结果。

输出描述：

输出二叉树的层次遍历结果。

示例1

输入：

CBEFDA CBAEDF
输出：

ABDCEF
说明：

二叉树为：
    A
   / \
  B   D
 /   / \
C   E   F

解题思路：考察对树的理解和运用。根据后序遍历和中序遍历的结果，重构出这棵二叉树，然后，使用层次遍历的方法遍历这棵二叉树，输出结果。

import sys
from collections import deque
 
def get_result(post, mid):
    queue = deque()
    ans = []
    devide_lr(post, mid, queue, ans)
 
    while queue:
        post, mid = queue.popleft()
        devide_lr(post, mid, queue, a