Rumah > Artikel > pembangunan bahagian belakang > php如何实现判断是否为二叉搜索树的后序遍历序列(代码)
本篇文章给大家带来的内容是关于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);
Atas ialah kandungan terperinci php如何实现判断是否为二叉搜索树的后序遍历序列(代码). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!