#10284. [NOIP2001 普及组] 数的计算
[NOIP2001 普及组] 数的计算
NOIP2001 普及组 - 求先序排列
任务总览
- 任务名称:求先序排列
- 时间限制:1 秒
- 内存限制:256 MiB
- 分数:100
题目描述
给出一棵二叉树的 中序遍历 和 后序遍历 序列,求出它的 先序遍历 序列。
- 约定:
- 树的节点用不同的大写字母表示。
- **节点个数不超过
8
**。
输入格式
- 两行字符串:
- 第一行:二叉树的 中序遍历 序列。
- 第二行:二叉树的 后序遍历 序列。
输出格式
- 一行字符串,表示二叉树的 先序遍历 序列。
样例
输入
BADC
BDCA
输出
ABCD
提示
**中序遍历 (Inorder):L → Root → R
后序遍历 (Postorder):L → R → Root
先序遍历 (Preorder)**:Root → L → R
题目分析
- 从后序遍历中找到根节点
- 后序遍历的最后一个节点 就是根节点。
- 在中序遍历中找到根节点的位置
- 根节点左侧部分是 左子树。
- 根节点右侧部分是 右子树。
- 递归构造左子树和右子树
- 先处理左子树,再处理右子树。
时间复杂度分析
- 由于节点数最大只有
8
,采用递归构建树的方式,时间复杂度为O(n^2)
完全可行。
结论
- 通过 后序遍历找到根节点,在 中序遍历确定子树,然后 递归构造先序遍历。
- 适用于 n ≤ 8 的小规模二叉树重建问题。