面试题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;
}

补充：软件开发 , C++ ,

上一个：面试题23：二叉树中和为某一值的路径
下一个：面试题21：从上往下打印二叉树