面試題22：二叉搜索樹的後序遍歷序列

分析：在後序遍歷得到的序列中，最後一個數字是樹的根結點的值，數組中前面的數字可分為兩個部分：第一部分是左子樹結點的值，它們都比根結點的值小，第二部分是右子樹結點的值，它們都比根結點的值大。

代碼：

#include "stdafx.h"
#include <iostream>
using namespace std;

bool VerifySequenceOfBST(int nSequence[], int nLength)
{
	if (nSequence == NULL || nLength <= 0)
	{
		return false;
	}

    int nRoot = nSequence[nLength - 1];
	int nIndex = 0;
	while (nSequence[nIndex] < nRoot)//左子樹中結點的值小於根節點的值
	{
		nIndex++;
	}

	for (int i=nIndex+1; i<nLength; i++)//右子樹中結點的值大於根節點的值
	{
		if (nSequence[i] < nRoot)
		{
			return false;
		}
	}

	bool bLeft = true;
	if (nIndex > 0)
	{
		bLeft = VerifySequenceOfBST(nSequence, nIndex);
	}

	bool bRight = true;
	if ((nIndex + 1) < nLength)
	{
		bRight = VerifySequenceOfBST(nSequence+nIndex, nLength - 1 - nIndex);
	}

	return  (bLeft && bRight);	
}

int _tmain(int argc, _TCHAR* argv[])
{
	int nArr1[7] = {5, 7, 6, 9, 11, 10, 8};//正確序列，有左右子樹
	cout << VerifySequenceOfBST(nArr1, 7) << endl;
	int nArr2[4] = {7, 4, 6, 5};//錯誤序列
	cout << VerifySequenceOfBST(nArr2, 4) << endl;
	int nArr3[3] = {3, 2, 1};//右單支
	cout << VerifySequenceOfBST(nArr3, 3) << endl;
	int nArr4[3] = {1, 2, 3};//左單支
	cout << VerifySequenceOfBST(nArr4, 3) << endl;
	int nArr5[1] = {1};//單個結點
	cout << VerifySequenceOfBST(nArr5, 1) << endl;
	system("pause");
	return 0;
}