侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【递归】求先序排列

GabrielxD
2022-12-19 / 0 评论 / 0 点赞 / 18 阅读 / 328 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-12-19,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

P1030 求先序排列


题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,且二叉树的节点个数 $ \le 8$)。

输入格式

共两行,均为大写字母组成的字符串,表示一棵二叉树的中序与后序排列。

输出格式

共一行一个字符串,表示一棵二叉树的先序。

样例 #1

样例输入 #1

BADC
BDCA

样例输出 #1

ABCD

提示

【题目来源】

NOIP 2001 普及组第三题

解题

方法一:递归

思路

【递归】从中序与后序遍历序列构造二叉树

代码

#include <iostream>
#include <cstring>
#include <unordered_map>
#include <limits>

using namespace std;

const int N = 10;
int n;
char io[N], po[N];
int lefts[N], rights[N], idx;
unordered_map<char, int> mp;

int build_tree(int st, int ed) {
    if (st > ed) return -1;
    char rv = po[idx];
    int ri = mp[rv];
    --idx;
    rights[ri] = build_tree(ri + 1, ed);
    lefts[ri] = build_tree(st, ri - 1);
    return ri;
}

void preorder(int i) {
    if (!~i) return;
    putchar(io[i]);
    preorder(lefts[i]);
    preorder(rights[i]);
}

int main() {
    scanf("%s\n%s", io, po);
    int n = strlen(io);
    idx = n - 1;
    for (int i = 0; i < n; ++i) mp[io[i]] = i;
    preorder(build_tree(0, n - 1));

    return 0;
}
0

评论区