二叉搜索树的后序遍历序列:
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路:
1.后序遍历是 左右中 , 最后一个元素是根结点
2.二叉搜索树,左子树<=根结点<=右子树
3.遍历数组,找到第一个大于root的位置,该位置左面为左子树,右面为右子树
4.遍历右子树,如果有小于root的返回false
5.递归左右左右子树
VerifySquenceOfBST(seq)
judge(seq,0,seq.size-1)
judge(seq,start,end)
if start>=end return true
root=seq[end]
index
for i=start;i<end;i++
if seq[i]>= root
index=i
break
for i=index;i<end;i++
if seq[i]<root
return false
return judge(seq,start,index-1) && judge(seq,index,end-1)
<?php
function judge($seq,$start,$end){
if(empty($seq)) return false;
//跳出条件
if($start>=$end) return true;
$root=$seq[$end];
$index=$end;
//找出第一个大于root的位置
for($i=$start;$i<$end;$i++){
if($seq[$i]>=$root){
$index=$i;
break;
}
}
//查找右子树中如果有小于root的返回false
for($i=$index;$i<$end;$i++){
if($seq[$i]<$root){
return false;
}
}
//短路语法递归调用
return judge($seq,$start,$index-1) && judge($seq,$index,$end-1);
}
function VerifySquenceOfBST($sequence)
{
return judge($sequence,0,count($sequence)-1);
}
$seq=array(1,2,3);
$bool=VerifySquenceOfBST($seq);
var_dump($bool);