#include <iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
int n,pos;
vector<int> pre,in,post;
void rec(int l,int r){
if (l>=r){
return;
}
int root =pre[pos++];
int m=distance(in.begin(),find(in.begin(),in.end(),root));
rec(l,m);
rec(m+1,r);
post.push_back(root);
}
void solve (){
pos = 0;
rec(0,pre.size());
for (int i = 0; i < n; ++i) {
if (i)
cout<<" ";
cout<<post[i];
}
cout<<endl;
}
int main() {
int k;
cin>>n;
for (int i = 0; i < n; ++i) {
cin>>k;
pre.push_back(k);
}
for (int i = 0; i < n; ++i) {
cin>>k;
in.push_back(k);
}
solve();
return 0;
}
if (l>=r){
return;
}
int root =pre[pos++];
int m=distance(in.begin(),find(in.begin(),in.end(),root));
rec(l,m);
rec(m+1,r);
这块可能 不是很理解 愚钝的我 自己大概模糊跑了一遍 现在讲一下我对
rec(l,m);
rec(m+1,r);
这个东西的理解
首先
rec(l,m);
这个是不断的找左字树 ， 一直找到最后的叶节点，此时 l-m=0
然后返回
rec(m+1,r);
那 在 (l-m=0)之前 L-M 肯定是等于1 的
因为他的左叶节点 和 他的父亲是 1 的差距
这就是
rec(m+1,r);
然后 就会 回溯到 父节点 就会 变成(m+1, r) 然后就会遍历父节点的右字数
感觉 很类似二分的思想(但不是精准的二分)
r - m+1就是 右字数的大小
说实话 能看懂我这的应该只有我自己
测试数据
9
1 2 3 4 5 6 7 8 9
3 2 5 4 6 1 8 7 9
运行结果
3 5 6 4 2 8 9 7 1
