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;
 }