Q24：二叉搜索树的后序遍历序列

Q：输入整数数组，判断该数组是否为某二叉搜索树的后序遍历结果。

题目里有几个字眼要求我们熟知，第一就是二叉搜索树，第二个就是后序遍历，第三就是它是树。

1）二叉搜索树：左孩子的值 < 根结点的值 < 右孩子的值

2）后序遍历：左->右->根

3）树：若一棵树是满足某一性质X的X树，则其子树若存在，则也定为满足X性质的X树。

好了，回到这个问题，通过2），我们可以从给定的数组中找到这个树的根，也就是数组的最后一个元素。通过1），我们可以将该树划分为左右两部分(也可能划分不了，就是不满足条件时)，根据3）我们可以对划分的左右子树进行递归操作。

那么这个问题就显得比较清晰了，至少不那么没有头绪了。

bool VerifySquenceOfBST(int sequence[], int length)
{
	if(NULL == sequence || 0 == length)
		return false;
	int root = length - 1;
	int left = 0;
	int right = 0;
	while(left < root && sequence[left] < sequence[root])
		left++;
	left--;
	for(right = left + 1; right < root; ++right)
		if(sequence[right] < sequence[root])
			return false;
	right = left + 1;
	bool bl = true;
	bool br = true;
	if(left > 0 )
		 bl = VerifySquenceOfBST(sequence, left);
	if(right < root)
		 br = VerifySquenceOfBST(sequence + left,root - left);
	return (bl && br);
}

Q24：二叉搜索树的后序遍历序列,布布扣,bubuko.com

Q24：二叉搜索树的后序遍历序列

原文：http://blog.csdn.net/shiquxinkong/article/details/22753795