建树的过程中实现中序遍历的一种巧妙方法:
中序 = 左 + 根 + 右
左和右分别通过递归实现 太好了这个方法
#include<iostream>
using namespace std;
const int N = 40;
int n;
int pre[N], post[N];
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;
int lcnt = dfs(l1 + 1, i, l2, l2 + i - l1 - 1, lin); // 前序l1是根节点 因此从l1 + 1作为左子树
int rcnt = dfs(i + 1, r1, l2 + i - l1, r2 - 1, rin); // 后序r2是根节点 因此肯定不能选
if(lcnt && rcnt){
cnt += lcnt * rcnt;
// 中序遍历 左 根 右 pre[l1]为当前的根结点
in = lin + to_string(pre[l1]) + ' ' + rin;
if(cnt > 1) break; //cnt > 1说明肯定不唯一 而且已经有一个成品树了 直接无需枚举后面的情况再次递归了
}
}
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 ans;
int cnt = dfs(0, n - 1, 0, n - 1, ans);
if(cnt > 1) puts("No");
else puts("Yes");
ans.pop_back();
cout << ans << endl;
return 0;
}