面试题整理7二叉搜索树的后序遍历序列

《剑指offer》面试题24：

题目： 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。

分析： 分析输入是整数数组，而不是整数数组和二叉树，所以不是说后序遍历一下二叉树与数组数组比较来判断是否是此二叉树的后序遍历序列。

            而是判断输入的整数数组是否是某一课二叉树的后序遍历序列的结果，如输入数组为{4, 8, 6, 12, 16, 14, 10}，则返回true，因为序列是如下图数的后序遍历结果；

           而输入数组{7, 4, 6, 5}，则由于没有二叉树与此序列对应，则返回false。

          由于后序遍历得到的序列中，最后一个数字是二叉树的根结点的&＃20540;。数组前面的数字可以分成两部分：左子树部分和右子树部分。左子树的数据&＃20540;都小于根结点的&＃20540;，右字数的数据&＃20540;都大于根结点的&＃20540;。采用递归的方法，从头扫描序列找到第一个大于根结点&＃20540;的数，此数之前的&＃20540;都为左子树部分，此数之后到最后一个数字前都是右子树部分，如果右子树部分出现小于根结点&＃20540;的&＃20540;则不符合规则，即返回false。否则递归左右子树。

（1） 自己写的代码：注意当查找的序列只有一个或者两个时，肯定是某个二叉树的后序序列；当查找的序列三个及以上时，查找到分割点时需要判断分割点的&＃20540;，注意不要越界。

bool IsPostTraverseOfBST(int sequence[], int length)
{
if(sequence == NULL || length <= 0)
return false;
return IsPostTraverseOfSubBST(sequence,0,length-1);

}
bool IsPostTraverseOfSubBST( int sequence[], int start, int end )
{
if( end - start <0 )
{
return false;
}
//only 1 or 2 elements
if( end - start <= 1)
{
return true;
}
int rootData = sequence[end];
int index = start;
// find the left subtree
for( ; index <= end-1; ++index )
{
if( sequence[index] > rootData )
{
break;
}
}
// find the right subtree
int midIndex = index++ ;
for( ; index<=end-1; ++index )
{
if( sequence[index] {
return false;
}
}
bool isLeft = true;
if( midIndex > 0 )
{
isLeft = IsPostTraverseOfSubBST( sequence,start, midIndex-1);
}
bool isRight = true;
if( midIndex {
isRight = IsPostTraverseOfSubBST( sequence,midIndex,end-1 );
}
return isLeft&&isRight;
}

（2）附上《剑指offer》中示例代码

bool VerifySquenceOfBST(int sequence[], int length)
{
if(sequence == NULL || length <= 0)
return false;
int root = sequence[length - 1];
// 在二叉搜索树中左子树的结点小于根结点
int i = 0;
for(; i {
if(sequence[i] > root)
break;
}
// 在二叉搜索树中右子树的结点大于根结点
int j = i;
for(; j {
if(sequence[j] return false;
}
// 判断左子树是不是二叉搜索树
bool left = true;
if(i > 0)
left = VerifySquenceOfBST(sequence, i);
// 判断右子树是不是二叉搜索树
bool right = true;
if(i right = VerifySquenceOfBST(sequence + i, length - i - 1);
return (left && right);
}

面试题整理7 二叉搜索树的后序遍历序列,布布扣,bubuko.com