#10284. [NOIP2001 普及组] 数的计算

[NOIP2001 普及组] 数的计算

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 的小规模二叉树重建问题。