[PHP]算法- 判断是否为二叉搜索树的后序遍历序列的PHP实现
程序员文章站
2022-04-11 14:59:09
二叉搜索树的后序遍历序列: 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 思路: 1.后序遍历是 左右中 , 最后一个元素是根结点 2.二叉搜索树,左子树=end return true root=seq[... ......
二叉搜索树的后序遍历序列: 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出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);