[PHP]算法- 判断是否为二叉搜索树的后序遍历序列的PHP实现

发布时间：2020-05-25 03:10:08 所属栏目：PHP 来源：互联网

导读：二叉搜索树的后序遍历序列：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。思路：1.后序遍历是左右中，最后一个元素是根结点2.二叉搜索树，左子树=根结点=右子

,思路：

1.<span style="color: #000000">后序遍历是 左右中 ， 最后一个元素是根结点

2.二叉搜索树，左子树<=根结点<=<span style="color: #000000">右子树

3.<span style="color: #000000">遍历数组，找到第一个大于root的位置，该位置左面为左子树，右面为右子树

4.<span style="color: #000000">遍历右子树，如果有小于root的返回false

5.<span style="color: #000000">递归左右左右子树
VerifySquenceOfBST(seq)

judge(seq,seq.size-1<span style="color: #000000">)

judge(seq,start,<span style="color: #008080">end<span style="color: #000000">)

<span style="color: #0000ff">if start>=<span style="color: #008080">end <span style="color: #0000ff">return <span style="color: #0000ff">true<span style="color: #000000">

root=seq[<span style="color: #008080">end<span style="color: #000000">]

index

<span style="color: #0000ff">for i=start;i<<span style="color: #008080">end;i++

<span style="color: #0000ff">if seq[i]>=<span style="color: #000000"> root

index=<span style="color: #000000">i

<span style="color: #0000ff">break

<span style="color: #0000ff">for i=index;i<<span style="color: #008080">end;i++

<span style="color: #0000ff">if seq[i]<<span style="color: #000000">root

<span style="color: #0000ff">return <span style="color: #0000ff">false

<span style="color: #0000ff">return judge(seq,index-1) && judge(seq,index,<span style="color: #008080">end-1)

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,$index-1) && judge($seq,$index,$end-1);
}

function VerifySquenceOfBST($sequence)
{
return judge($sequence,count($sequence)-1);
}

$seq=array(1,2,3);
$bool=VerifySquenceOfBST($seq);
var_dump($bool);

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!