AcWing 1631. 后序遍历
原题链接
简单
作者:
YAX_AC
,
2024-11-28 10:29:48
,
所有人可见
,
阅读 4
//Traversals遍历 Pre- and Post-order Traversals前序和后序遍历
//be determined by由…决定 pair of一对 sequences顺序次序
//postorder后序 inorder 中序 preorder先序 traversal遍历
//先序:根左右
//中序:左根右
//后序:左右根
#include<iostream>
#include<unordered_map>
using namespace std;
const int N = 50010;
int n;
int pre[N],in[N];
unordered_map<int,int> pos;//中序遍历中数值与位置的映射
int post;//post:记录后序的第一个数
void build(int il,int ir,int pl,int pr)
{
if(il>ir) return;
int root = pre[pl];
int k = pos[root]; //根节点在中序中的位置
//pl+1:去掉前序的根节点
build(il,k-1,pl+1,pl+1+k-1-il);//遍历左子树:中序遍历的左[il,k-1],前序遍历的左[pl+1,pl+1+k-1-il]
build(k+1,ir,pl+1+k-1-il+1,pr);//遍历右子树:中序遍历的右[k+1,ir],前序遍历的右[pl+1+k-1-il+1,pr]
if(!post) post = root;//最左的孩子就是后序遍历的开始
}
int main()
{
cin>>n;
for(int i = 0; i<n; i++) cin>>pre[i];
for(int i = 0; i<n; i++)
{
cin>>in[i];
pos[in[i]] = i;
}
build(0,n-1,0,n-1);
cout<<post;
return 0;
}