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

题目描述

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

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

输入描述

每个输入文件一行，第一个字符串表示后序遍历结果，第二个字符串表示中序遍历结果。（每串只包含大写字母）

中间用单空格分隔。

输出描述

输出仅一行，表示层序遍历的结果，结尾换行。

用例

题目解析

二叉树的三种遍历方式：

• 前（根）序遍历：根左右
• 中（根）序遍历：左根右
• 后（根）序遍历：左右根

可以发现，其实前、中、后指的是根的位置，而左右的顺序是不变的，即总是先左后右。

比如，下面是一个最简单的二叉树结构

其前序遍历结果为：ABC，中序遍历结果为BAC，后序遍历结果为BCA。

而层序遍历，指的是，从树的顶层开始向下，每层中按照从左向右的顺序遍历节点，因此上图层序遍历结果为ABC。

可能有人会将层序遍历和前序遍历混淆，但是二者是不同的，比如：

前序遍历结果为：ABDC

层序遍历结果为：ABCD 

有了以上关于二叉树遍历的知识后，我们就可以进行用例分析了，用例输入提供了一个二叉树的

后序遍历CBEFDA，以及中序遍历CBAEDF的结果。

首先，我们可以根据后序遍历，快速找到树根，即CBEFDA中的A，因为根据左右根遍历顺序，最后一个遍历元素肯定是这颗树的根节点。

而找到根节点A后，我们又可以在中序遍历的左根右遍历顺序，找到A根的左、右子树，即中序遍历中A节点的左边就是A根的左子树，右边就是A根的右子树。

而找到左右子树后，我们可以根据后序遍历，再分别找到左、右子树的根，然后再根据中序遍历结果，再找出左子树根的左右子树，以及右子树的左右子树。

过程如下图所示：

当我们找到的根的左右子树只有1个节点，或没有节点时，则可以停止递归。

当递归完成后，就还原出了一颗树，接下来根据层序遍历规则，即可以得到结果：ABDCEF。

本题解题，貌似需要深度优先搜索DFS来生成树结构，其实不然，我们完全可以改变策略，使用广度优先搜索BFS，来实现层序遍历效果，避免构造树结构，进行二次搜索。

BFS实现层序遍历的逻辑如下：

首先，根据后序遍历结果，找到根A，然后根据中序遍历结果找到根A的左、右子树。

然后，我们就得到了根A左、右子树各自的长度

根据左右子树的长度，我们就可以从后序遍历结果中，截取出左、右子树，然后又可以得到左、右子树各自的根（即最后一个元素）。

我们，每次优先遍历子树的根，然后再遍历子树的左右子树。 

import Foundation

func ODTest_2_50() {
    print("输入描述")
    print("每个输入文件一行，第一个字符串表示后序遍历结果，第二个字符串表示中序遍历结果。（每串只包含大写字母）中间用单空格分隔")
    let str = (readLine() ?? "").split(separator: " ").map { String($0) }
    var post = str[0]
    var mid = str[1]
    p