本文共 825 字，大约阅读时间需要 2 分钟。

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

转载地址：http://rrlji.baihongyu.com/