二叉树的广度优先遍历 - 华为OD统一考试(D卷)

OD统一考试（D卷）

分值： 200分

题解： Java / Python / C++

题目描述

有一棵二叉树，每个节点由一个大写字母标识(最多26个节点）。

现有两组字母，分别表示后序遍历（左孩子->右孩子->父节点）和中序遍历（左孩子->父节点->右孩子）的结果，请输出层次遍历的结果。

输入描述

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

输出描述

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

示例1

输入：
CBEFDA CBAEDF输出：
ABDCEF说明：
二叉树为：A/ \B   D/   / \
C   E   F

题解

• 题目类型: 该题目是关于树的构建和遍历的问题。
• 解题思路:
  • 首先需要根据给定的后序遍历和中序遍历构建二叉树。
  • 构建二叉树的过程可以通过递归实现。在递归中，根据后序遍历的最后一个节点确定根节点，在中序遍历中找到对应的根节点位置，