NC16692 [NOIP2001]求先序排列
题目
题目描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度 ≤ 8）。
输入描述
2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。
输出描述
1行，表示一棵二叉树的先序。
示例1
输入
BADC
BDCA
输出
ABCD
题解
思路
知识点：递归，分治。
后序排列为左右根，中序排列为左根右。每次找到当前子树的根节点，即后序右端节点，然后从中序找到这个节点划分为左子树和右子树，递归找根即可。
时间复杂度 /(O(n /log n)/)
空间复杂度 /(O(n)/)
代码
#include <bits/stdc++.h>
using namespace std;
string io, lo;
void fo(int l1, int r1, int l2, int r2) {
if (l1 > r1)return;
cout << lo[r2];
int pos = io.find(lo[r2]);
fo(l1, pos - 1, l2, l2 + pos - l1 - 1);
fo(pos + 1, r1, l2 + pos - l1, r2 - 1);
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> io >> lo;
fo(0, io.length() - 1, 0, io.length() - 1);
cout << '/n';
return 0;
}
原创文章，作者：745907710，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/269701.html