输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回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);
}
在Java中实现的二叉树结构