이 기사의 내용은 PHP가 이진 검색 트리인지 확인하기 위해 후위 순회 시퀀스(코드)를 구현하는 방법에 대한 것입니다. 필요한 친구는 이를 참조할 수 있습니다. 도움이 됩니다.
이진 탐색 트리의 후위 순회 순서:
정수 배열을 입력하고 그 배열이 특정 이진 탐색 트리의 후위 순회 결과인지 확인합니다. 그렇다면 Yes를 출력하고, 그렇지 않으면 No를 출력합니다. 입력 배열의 두 숫자가 서로 다르다고 가정합니다.
생각하기:
1. 후위 순회는 왼쪽과 오른쪽에 있으며 마지막 요소는 루트 노드입니다.
2. 이진 검색 트리, 왼쪽 하위 트리 <= 루트 노드<= 오른쪽 하위 트리
3. , 루트보다 큰 첫 번째 위치를 찾습니다. 이 위치의 왼쪽 하위 트리가 오른쪽 하위 트리입니다. 4. 루트보다 작은 하위 트리가 있으면 false를 반환합니다. 왼쪽 및 오른쪽 하위 트리를 반복합니다.
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);
위 내용은 이진 검색 트리의 후순 순회 시퀀스인지 확인하기 위해 PHP를 구현하는 방법(코드)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!