当前位置：首页 > news >正文

PAT 1119 Pre- and Post-order Traversals

news 2026/6/2 5:36:11

这一题的大意是说给出前序遍历和后序遍历，让我们找是否构造一个唯一的二叉树，
如果可以返回Yes，并输出中序遍历序列，如果不可以，那么就是输出No，并输出其中一种情况的中序遍历序列。
我们都知道通过前序和后序是无法确定一棵二叉树的，因为我们无法确定左子树和右子树分别是哪些，它不像中序遍历+后序遍历一样，可以找到根节点后，通过根节点把左右子树分开，而前序和后序是无法实现的，我们无法确定哪些是左子树，哪些是右子树。
因此，我们要假设某一个节点（前序节点中根节点的后面的那一个节点）是左子树，用这种方法来建树，如果在建树的过程中如果存在前序遍历的左子树和后序遍历的右子树相等（也就是后序遍历根节点的前一个节点和前序遍历的根节点的后一个节点相同。）如果一样，说明不能构成唯一的序列，因为后序遍历根节点的前一个节点和前序遍历的根节点的后一个节点相同说明这个节点充当左子树和充当右子树是一样的。因此不唯一。
我们通过遍历序列来建树的方法是有套路的：

boolflag=1;//假设为一node*build(intprestart,intpreend,intpoststart,intpostend){if(prestart>preend){returnnullptr;}if(prestart==preend){//为啥在只有一个节点的时候不能继续往下划分node*root=new(node);root->data=pre[prestart];root->l=nullptr;root->r=nullptr;returnroot;}node*root=new(node);root->data=pre[prestart];root->l=nullptr;root->r=nullptr;intx=pre[prestart+1];//左子树的根节点if(pre[prestart+1]==post[postend-1]){flag=0;}intindex;for(inti=poststart;i<=postend;i++){if(post[i]==x){index=i;break;}}intlen=index-poststart+1;//这就是左子树的长度root->l=build(prestart+1,prestart+1+len-1,poststart,poststart+len-1);root->r=build(prestart+1+len,preend,poststart+len,postend-1);returnroot;}

这与之前的前序+中序/中序+后序建树的方法不同的是：

if(prestart==preend){node*root=new(node);root->data=pre[prestart];root->l=nullptr;root->r=nullptr;returnroot;}

当子树只有一个节点的时候，我们需要特判直接返回。
为什么？因为在后面建树的时候：

intx=pre[prestart+1];//左子树的根节点

这里很明显越界了，往后的遍历也会出错，后面在递归划分左右子树也是错的，因此我们要在只有一个节点的时候特判返回
其他和中序+后序建树是类似的。
可以看一下这篇博客：

PAT 1020 Tree Traversals

因此这一题的完整代码就如下啦：

#include<bits/stdc++.h>#include<iostream>usingnamespacestd;intN;vector<int>pre;vector<int>post;structnode{intdata;structnode*l;structnode*r;};boolflag=1;//假设为一node*build(intprestart,intpreend,intpoststart,intpostend){if(prestart>preend){returnnullptr;}if(prestart==preend){//为啥在只有一个节点的时候不能继续往下划分node*root=new(node);root->data=pre[prestart];root->l=nullptr;root->r=nullptr;returnroot;}node*root=new(node);root->data=pre[prestart];root->l=nullptr;root->r=nullptr;intx=pre[prestart+1];//左子树的根节点if(pre[prestart+1]==post[postend-1]){flag=0;}intindex;for(inti=poststart;i<=postend;i++){if(post[i]==x){index=i;break;}}intlen=index-poststart+1;//这就是左子树的长度root->l=build(prestart+1,prestart+1+len-1,poststart,poststart+len-1);root->r=build(prestart+1+len,preend,poststart+len,postend-1);returnroot;}boolf=0;voidinorder(node*root){if(root->l!=nullptr)inorder(root->l);if(root!=nullptr){if(f==0){cout<<root->data;f=1;}elsecout<<" "<<root->data;}if(root->r!=nullptr)inorder(root->r);}intmain(){intN;cin>>N;for(inti=0;i<N;i++){intx;cin>>x;pre.push_back(x);}for(inti=0;i<N;i++){intx;cin>>x;post.push_back(x);}node*root=build(0,N-1,0,N-1);//cout<<"1"<<endl;if(flag==1){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}inorder(root);cout<<endl;return0;}