二叉搜索树的后序遍历序列详述

题目:输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。思路：在后序遍历得到的序列中，最后一个数字是树的根结点的值。数组中前面的数字可以分为两部分:第一部分是左子树结点的值，它们都比根结点的值小；第二部分是右子树结点的值，它们都比根结点的值大。代码如下：bool VerifyBST（int squence[], int length）
{
if （squence==NULL||length<=0）
return false;
//序列中最后一个数字是根结点的值
int root=squence[length-1];
//二叉搜索树中左子树的结点值小于根结点
int i=0;
for （ ; i<length-1; i++）
{
if （squence[i]>root）
break;
}
//二叉搜索树中右子树的结点值大于根据点
int j=i;//i为右子树的根结点值
for（ ; j<length-1; j++）
{
if （squence[j]<root）
return false;
}
//判断左子树是不是二叉搜索树
bool left=true;
if （i>0）
{
left=VerifyBST（squence,i）;
}
//判断右子树是不是二叉搜索树
bool right=true;
if （j<length-1）
{
right=VerifyBST（squence,length-1-i）;
}
return （left&&right）;
}二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm轻松搞定面试中的二叉树题目 http://www.linuxidc.com/linux/2014-07/104857.htm本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-05/117699.htm