本篇文章给大家带来的内容是关于php如何实现判断是否为二叉搜索树的后序遍历序列（代码），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。
二叉搜索树的后序遍历序列：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出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); 
