L2-004 这是二叉搜索树吗？ (25 分)——思路不懂得看这里

题目链接

文章目录

• • 说明
  • 思路
  • AC代码

说明

思路参考大佬博客，

不过我开始没懂，其实最后还是我的学姐把我讲懂的

思路

首先，我们解释下镜像二叉搜索树。其实即使更改了二叉搜索树得定义：左子树得所有节点值大于等于根节点得值，右子树的所有节点值小于根节点值，左右子树也是二叉搜索树。

如图所示

好了，其实根据二叉搜索树的前序及其定义以及可以确定树的形状了，

如图所示

盗的学姐的图

现在要求后序遍历，我们可以根据前序遍历，进行划分左右子树，然后递归左右根的进行保存根节点，这样就得到了后序遍历。

代码注释有详解

AC代码

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5+9;
int pre[N];
vector<int>post;
bool isMirror;
void getpost(int l,int r)
{
	if(l>r) return ;
	int i=l+1,j=r;
	//线判断是否炜镜像，如果不是镜像
	//那么左子树的值都是小于根节点的，
	//右子树都是大于等于根节点的 
	// 镜像则相反 
	if(!isMirror)
	{
		//这里要注意边界条件是i<=r,并且j>l
		//可以参考数据 6 5 
		while(i<=r&&pre[i]<pre[l]) i++;
		while(j>l&&pre[j]>=pre[l]) j--;
	}
	else 
	{
		while(i<=r&&pre[i]>=pre[l]) i++;
		while(j>l&&pre[j]<pre[l]) j--;
	}
	//如果是二叉搜索树的前序遍历，那么，经过上述划分后i-j肯定为1
	//大家随便模拟一个例子即可。 
	if(i-j!=1) return ;
	getpost(l+1,j);//左 
	getpost(i,r);//右 
	//printf("%d ",pre[l]);
	post.push_back(pre[l]);//根 
}
int main()
{
	int n;
	cin>>n;
	for(int i=0; i<n; i++) scanf("%d",pre+i);
	getpost(0,n-1);
	if(post.size()!=n)
	{
		isMirror=true;
		post.clear();//这里要注意清空post 
		getpost(0,n-1);
	}
	//puts("");
	if(post.size()==n)
	{
		printf("YES\n");
		for(int i=0; i<n; i++)
		{
			printf("%d",post[i]);
			if(i<n-1) printf(" ");
		} 
	}
	else printf("NO\n");
	return 0;
 }