输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。二叉搜索树就是这个二叉树的左子树的所有节点都比根节点小,右子树的所有节点都比根节点大。我们知道后序遍历的最后一个节点一定是根节点,因此根据根节点和二叉搜索树的大小关系,可以将序列从头开始和根节点比较,小的就是左子树,大的就是右子树。依次做下去,就能判断出是否是二叉搜索树。
bool VerifySquenceOfBST(vector<int> sequence) {
return post_array(sequence,0,sequence.size()-1);
}
bool post_array(vector<int> a, int start, int end) {
int i = 0, j = 0;
//当树只有一个节点的时候,一定是平衡树
if (start == end)
return true;
//以根节点为基础,找到比根节点小的左子树的所有元素
for (i = start; i < end; i++) {
if (a[i] > a[end])
break;
}
//与左子树相同,找到右子树
for (j = i; j < end; j++)
if (a[j] < a[end])
break;
//如果右子树里面有比根节点小的,说明不是平衡树
if (j != end)
return false;
//这里必须初始化为true,否则在不执行下面其中之一的判断是,会导致程序错误
bool left = true,right = true;
//对找到的左子树和右子树递归查找
if(i>start)
//这里我一开始弄成了start+i-1,后来发现i是以start开始的
left = post_array(a,start,i-1);
if(i < end)
right = post_array(a,i,end-1);
return left && right;
}