【二叉树】L2-004 这是二叉搜索树吗

谁践踏了优雅 2024-03-23 13:03 56阅读 0赞

[题目详情 - L2-004 这是二叉搜索树吗？ (pintia.cn)][- L2-004 _ _pintia.cn]

题意：

![c391d99fd2a34121b82d01b910eaab8f.png][]

思路：

**二叉树递归一般步骤：**

**1.确定左儿子和右儿子对应区间**

**2.递归**

**3.记录结点**

题目给定的序列是前序遍历的结果，要我们求其后序遍历的结果

那么在递归过程中肯定要先去确定根节点的左儿子和右儿子对应的区间

因为它是一棵二叉搜索树，所以左儿子和右儿子对应的区间都确定了

左儿子里所有结点都比根节点小，右儿子里所有结点都比根节点大

如果是镜像就反一下即可

Code：

#include <bits/stdc++.h>
    #define int long long
    
    using namespace std;
    const int mxn=2e2+10;
    const int mxe=4e4+10;
    const int Inf=1e18;
    
    vector<int> v;
    int n,ok=0;
    int p[mxn];
    void dfs(int l,int r){
    	if(l>r) return;
    	int tl=l+1,tr=r;
    	if(!ok){
    		while(tl<=r&&p[tl]<p[l]) tl++;
    		tl--;
    		while(tr>=l+1&&p[tr]>=p[l]) tr--;
    		tr++;
    	}else{
    		while(tl<=r&&p[tl]>=p[l]) tl++;
    		tl--;
    		while(tr>=l+1&&p[tr]<p[l]) tr--;
    		tr++;
    	}
    	if(tr-tl!=1) return;
    	dfs(l+1,tl);
    	dfs(tl+1,r);
    	v.push_back(p[l]);
    }
    void solve(){
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>p[i];
    	dfs(1,n);
    	if(v.size()!=n){
    		ok=1;
    		v.clear();
    		dfs(1,n);
    	}
    	if(v.size()!=n){
    		cout<<"NO"<<'\n';
    		return;
    	}
    	cout<<"YES"<<'\n';
    	for(int i=0;i<v.size();i++) cout<<v[i]<<" \n"[i==v.size()-1]; 
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[- L2-004 _ _pintia.cn]: https://pintia.cn/problem-sets/994805046380707840/exam/problems/994805070971912192
[c391d99fd2a34121b82d01b910eaab8f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/a8a229981a89462e82b51dc1b37c6c2b.png