题解：洛谷 P1030 [NOIP 2001 普及组] 求先序排列

【题目来源】

洛谷：[P1030 NOIP 2001 普及组] 求先序排列 - 洛谷

【题目描述】

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 ≤8）。

【输入】

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

【输出】

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

【输入样例】

BADC
BDCA

【输出样例】

ABCD

【解题思路】

【算法标签】

《洛谷 P1030 求先序排列》 #字符串# #树形数据结构# #递归# #深度优先搜索DFS# #NOIP普及组# #2001#

【代码详解】

#include <bits/stdc++.h>
using namespace std;string b;  // 前序遍历序列
string c;  // 中序遍历序列
int n;     // 序列长度// 递归构建二叉树并输出后序遍历
void dfs(string x)
{// 空节点直接返回if (x.size() == 0)return;// 叶子节点直接输出if (x.size() == 1){cout << x;return;}int pos = -1;  // 记录根节点在中序序列中的位置// 从后往前在中序序列中查找当前树的根节点for (int i = n - 1; i >= 0 && pos == -1; i--){for (int j = 0; j < x.size() && pos == -1; j++){if (x[j] == c[i])  // 找到根节点pos = j;}}// 输出根节点（后序遍历的顺序）cout << x[pos];// 递归处理左子树dfs(x.substr(0, pos));// 递归处理右子树dfs(x.substr(pos + 1, x.size() - pos - 1));
}int main()
{// 输入前序和中序遍历序列cin >> b >> c;n = c.size();  // 获取序列长度// 开始递归构建树结构并输出后序遍历dfs(b);return 0;
}

【运行结果】

BADC
BDCA
ABCD