【递归】求先序排列

题目

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;
}