검지offer 시리즈: 두 갈래 검색 트리의 뒷순서 반복 시퀀스
5499 단어 검지offer 알고리즘
묘사
정수 그룹을 입력하여 이 그룹이 어떤 두 갈래 검색 트리의 후순으로 옮겨다니는 결과인지 판단하십시오.예이면 Yes를 내보내고 그렇지 않으면 No를 내보냅니다.입력한 그룹의 임의의 두 숫자가 서로 다르다고 가정하십시오.
코드
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length==0){
return false;
}
int i = sequence.length-1;
return judge(sequence,0,i);
}
boolean judge(int[] arr,int left,int right){
if(left>=right){
return true;
}
int root = arr[right];
int i = left;
while(arr[i]<root){
i++;
}
int j = i;
while(j<right){
if(arr[j]<root){
return false;
}
j++;
}
return judge(arr,0,i-1)&&judge(arr,i,j-1);
}
}
소감
두 갈래 나무의 후속은 좌우 뿌리를 두루 훑어보기 때문에 뒤에서 앞으로 차례대로 뿌리 오른쪽 나무 왼쪽 나무는 왼쪽 나무가 모두 뿌리보다 작고 오른쪽 나무가 모두 뿌리보다 크며 하위 나무도 위의 요구에 부합한다는 것을 검증해야 한다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
검지offer 시리즈: 두 갈래 검색 트리의 뒷순서 반복 시퀀스정수 그룹을 입력하여 이 그룹이 어떤 두 갈래 검색 트리의 후순으로 옮겨다니는 결과인지 판단하십시오.예이면 Yes를 내보내고 그렇지 않으면 No를 내보냅니다.입력한 그룹의 임의의 두 숫자가 서로 다르다고 가정하십시오...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
