PAT 1167 Cartesian Tree（30）

题目

代码

参考代码（有注释）

#include<bits/stdc++.h>
using namespace std;
vector<int> ins;//中序遍历 
struct node{
    
    int index, id;
};
vector<node> ans;
bool cmp(node a, node b){
    
    return a.index < b.index;
}
void levelorder(int inl, int inr, int root, int index){
    //index层序遍历的下标 
    if(inl > inr || root < inl || root > inr) return;//超出边界 
    int i = inl, j = root + 1,minl = ins[inl], minr = ins[root + 1];//左右界限的下标及其对应的值 
    for(int l = inl;  l<root; l++)
        if(ins[l] < minl){
    //左侧最小值 
            i = l;
            minl = ins[l];
        }
    for(int p = root + 1;  p<= inr; p++){
    //右侧最小值 
        if(ins[p] < minr){
    
            j = p;
            minr = ins[p];
        }
    }
    ans.push_back({
    index, ins[root]});
    levelorder(inl, root - 1, i, 2 * index);//递归左子树 
    levelorder( root+ 1, inr, j, 2 * index + 1);//递归右子树 
}
int main(){
    
    int n, root, minn = INT_MAX, tag;
    cin >> n;
    ins.resize(n + 1);
    for(int i = 1; i <= n; i++){
    
        cin >> ins[i];
        if(ins[i] < minn){
    //找到根节点 
            minn = ins[i];
            root=i;
        }   
    } 
    levelorder(1, n, root, 1);
    sort(ans.begin(),ans.end(), cmp);
    for(int i = 0 ; i < ans.size(); i++)
    printf("%d%c", ans[i].id, i < ans.size() - 1? ' ' : '\n');
    return 0;
}

复现代码

#include<bits/stdc++.h>
using namespace std;
vector<int> in;
struct node{
    
	int val,index;
};
vector<node> ans;
bool cmp(node x,node y){
    
	return x.index<y.index;
}
void levelorder(int l,int r,int root,int index){
    
	if(l>r||root<l||root>r) return;
	int posl=l,posr=r;
	for(int i=l+1;i<root;i++){
    
		if(in[i]<in[posl]){
    
			posl=i;
		}
	}
	for(int i=r-1;i>root;i--){
    
		if(in[i]<in[posr]){
    
			posr=i;
		}
	}
	ans.push_back({
    in[root],index});
// cout<<in[root]<<endl;
	levelorder(l,root-1,posl,index*2);
	levelorder(root+1,r,posr,index*2+1);
}
int main()
{
    
	int n,minn=INT_MAX,root=-1;
	cin>>n;	
	in.resize(n);
	for(int i=0;i<n;i++){
    
		cin>>in[i];
		if(in[i]<minn){
    
			minn=in[i];
			root=i;
		}
	}
// cout<<minn<<" "<<root<<endl;
	levelorder(0,n-1,root,1);
	sort(ans.begin(),ans.end(),cmp);
	for(int i=0;i<ans.size();i++){
    
		cout<<ans[i].val;
		if(i!=ans.size()-1) cout<<" ";
	}
} 

参考文章

2019年12月PAT甲级 第四题 Cartesian Tree（1167）题解