검지offer_정수 그룹을 입력하여 이 그룹이 어떤 두 갈래 검색 트리의 뒤서열을 훑어보는 결과인지 판단하십시오...

3064 단어
제목 설명
정수 그룹을 입력하여 이 그룹이 두 갈래 검색 트리의 뒷순서가 두루 흐르는 결과인지 판단합니다.예일 경우 출력 Yes, 그렇지 않으면 출력 No.입력한 그룹의 임의의 두 숫자가 서로 다르다고 가정하십시오.
앞서 소닌 필기시험에서 이 문제를 만났는데 당시 두 갈래 검색 트리는 모두 만 두 갈래 나무라고 생각했기 때문에 귀속 과정에서 수조에 대한 구분은 만 두 갈래 나무의 특성으로 구분되었다.큰 실수, 큰 실수!
본고는 귀속 사상을 이용하여 뿌리 노드의 왼쪽 나무 원소가 뿌리 노드보다 작고 오른쪽 나무 원소가 뿌리 노드보다 큰지 판단하는 것이다.좌우 트리에 대한 구분에 중점을 두다.
1. 0위부터 루트 노드보다 큰 원소를 찾아 이 위치 i를 기록한다.이 위치에 있기 전에 모두 왼쪽 트리에 속한다. (이 때 왼쪽 트리가 뿌리 노드보다 작다고 단정되었다.) 2.오른쪽 트리가 모두 노드보다 큰지 확인하기 (i위부터 루트 노드 앞까지) 3.좌우 자수가 모두 두 갈래 수색수에 속하는지 판단한다.
코드는 다음과 같습니다.
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null||sequence.length==0){
            return false;
        }
        boolean res =getRes(sequence,0,sequence.length-1);
        return res;
    }

    public boolean getRes(int[] s,int start,int end){
        int j=0;
        int i=0;
        if(end-start<=1){
            return true;
        }
        for( i=start;iif(s[i]>s[end]){
                break;
            }
        }

        for(j=i;jif(s[j]return false;
            }
        }
        boolean left=true;
        boolean right=true;
        if(i>0){
            left = getRes(s,start,i-1);
        }
        if(i1){
            right=getRes(s,i,end-1);
        }
        return left&&right;
    }
}

다음으로 전송:https://www.cnblogs.com/lingongheng/p/6444229.html
【DP】【귀속】분리와 합체
노드 HarperDB REST API

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage