《劍指offer》:[24]判斷一個序列是否為二叉樹的後序周遊序列

題目：輸入一個整數，判斷該數組是不是某二叉搜尋樹的後序周遊的結果。如果是則傳回true，否傳回false。假設輸入的數字互不重複。

在後續周遊中，最後一個數字是根結點，将數組中的數字分為兩部分：第一部分是左子樹的值，它的值都比根結點小；另一部分是右子樹的值，它的值都比根結點大；

以上面的二叉樹為例：後續周遊[3,6,4,10,14,12,8]的最後一個結點是8，是以在這個數組中，3,6,4都比8小時該數的左子樹；而10，14，12都比8大，是該樹的右子樹。我們以同樣的方法來分析其左子樹和右子樹3,6,4，其中4将左子樹分為3和6兩部分；12将右子樹10和14分為兩部分。是以這個序列就是一個後續周遊序列。但是[7,4,5,6]就不是它的一個後續周遊序列。因為6大于7，是以也就是說7,4,5都是其右子樹，但是很不幸還有4比6小，是以不可能是一個後續周遊。

具體實作代碼如下：

#include <iostream>
using namespace std;
struct BinartyTree
{
	int data;
	BinartyTree *pLeft;
	BinartyTree *pRight;
};
BinartyTree *pRoot1=NULL;
int arr2[7]={5,6,4,10,14,12,8};//YES
int arr3[7]={5,6,4,10,12,7,8};  //NO


bool VerifySequenceOfBST(int *array,int length)
{
	if(NULL==array || length<=0)
		return false;
	int root=array[length-1];
	int i=0;//左子樹的結點小于根節點；
	for(;i<length-1;i++)
	{
		if(array[i]>root)
			break;//找完了全部的左子樹的序列；
	}
	int j=i;//右子樹的結點大于根結點；
	for(;j<length-1;j++)
	{
		if(array[j]<root)
			return false;
	}
	bool left=true;
	if(i>0)
		left=VerifySequenceOfBST(array,i);
	bool right=true;
	if(j<length-1)
		right=VerifySequenceOfBST(array+i,length-i-1);
	return left && right;
}
int main()
{
	if(VerifySequenceOfBST(arr2,7))
		cout<<"YES!"<<endl;
	else
		cout<<"NO"<<endl;


	if(VerifySequenceOfBST(arr3,7))
		cout<<"YES!"<<endl;
	else
		cout<<"NO"<<endl;


	system("pause");
	return 0;
}
           

運作結果：

小結：不管是分析是否是前序還是後續，我們都可以先找到二叉樹的根結點，再基于根結點将整棵樹拆分為左子樹和右子樹序列。接下來再遞歸處理兩個子序列即可。

采用“分治法”的思想，解決這樣的問題。