AcWing 1609. 前序和后序遍历
原题链接
中等
作者:
0x3f3f3f3f
,
2022-02-15 18:56:23
,
所有人可见
,
阅读 227
题目描述
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 40;
int n;
int pre[N], post[N], inorder[N];
// lin, rin, in 后面都会自动多一个空格
// 因为 在叶子节点的时候, in = lin + to_string(pre[l1]) + " " + rin
// 实际上就是 to_string(pre[l1]) + " ",一个数字 + 一个空格的形式。
int dfs(int l1, int r1, int l2, int r2, string &in) {
// 空树一定可以建成
if (l1 > r1)
return 1;
// 如果不符合前序和后序遍历的性质,那么无法建树
if (pre[l1] != post[r2])
return 0;
int cnt = 0;
//枚举,左子树包含的节点数量
for (int i = l1; i <= r1; i++) {
string lin, rin;
// 左子树空树的情况也可以枚举到
// 不能是 i + 1,因为要考虑左右子树不存在的情况
int lcnt = dfs(l1 + 1, i, l2, l2 + i - l1 - 1, lin);
int rcnt = dfs(i + 1, r1, l2 + i - l1 - 1 + 1, r2 - 1, rin);
// 如果左右子树都可以建立,则说明当前树可以建立
if (lcnt && rcnt) {
// pre[l1] 为当前的根节点。
in = lin + to_string(pre[l1]) + ' ' + rin;
cnt += lcnt * rcnt;
if (cnt > 1)
break;
}
}
return cnt;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> pre[i];
for (int i = 0; i < n; i++)
cin >> post[i];
string in;
int cnt = dfs(0, n - 1, 0, n - 1, in);
//如果不唯一输出No
if (cnt > 1)
puts("No");
else
puts("Yes");
// pop_back 将 string 最后的空格删去
in.pop_back();
cout << in << endl;
return 0;
}