本篇文章给大家带来的内容是关于php如何实现判断是否为二叉搜索树的后序遍历序列（代码），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。
二叉搜索树的后序遍历序列：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。本&文来源gao@daima#com搞(%代@#码网@
思路：
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)
<?phpfunction 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);
以上就是php如何实现判断是否为二叉搜索树的后序遍历序列（代码）的详细内容，更多请关注搞代码gaodaima其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：php如何实现判断是否为二叉搜索树的后序遍历序列（代码）
转载请注明原文链接：php如何实现判断是否为二叉搜索树的后序遍历序列（代码）
