NOIP2001 普及组 - 求先序排列

任务总览

• ​任务名称​：求先序排列
• ​时间限制​：1 秒
• ​内存限制​：256 MiB
• ​分数​：100

题目描述

给出一棵二叉树的 中序遍历 和 后序遍历 序列，求出它的 先序遍历 序列。

• ​约定​：
  • 树的节点用不同的大写字母表示。
  • ​**节点个数不超过 8**​。

输入格式

• ​两行字符串​：
  • ​第一行​：二叉树的 中序遍历 序列。
  • ​第二行​：二叉树的 后序遍历 序列。

输出格式

• ​一行字符串​，表示二叉树的 先序遍历 序列。

样例

输入

BADC
BDCA

输出

ABCD

提示

​**中序遍历 (Inorder)​：L → Root → R ​后序遍历 (Postorder)​：L → R → Root ​先序遍历 (Preorder)**​：Root → L → R

题目分析

1. 从后序遍历中找到根节点
   • 后序遍历的最后一个节点 就是根节点。
2. 在中序遍历中找到根节点的位置
   • 根节点左侧部分是 ​左子树​。
   • 根节点右侧部分是 ​右子树​。
3. 递归构造左子树和右子树
   • 先处理左子树，再处理右子树。

时间复杂度分析

• 由于节点数最大只有 8，采用递归构建树的方式，时间复杂度为 O(n^2)​完全可行​。

结论

• 通过 ​后序遍历找到根节点​，在 ​中序遍历确定子树​，然后 ​递归构造先序遍历​。
• 适用于 n ≤ 8 的小规模二叉树重建问题。