제목 설명

정수 그룹을 입력하여 이 그룹이 두 갈래 검색 트리의 뒷순서가 두루 흐르는 결과인지 판단합니다.예일 경우 출력 Yes, 그렇지 않으면 출력 No.입력한 그룹의 임의의 두 숫자가 서로 다르다고 가정하십시오.

문제 풀이 사고방식

뒤의 서열을 되돌아보는 서열의 특성: 마지막 원소는 뿌리이고 앞의 서열과 뿌리보다 작은 앞부분(왼쪽 나무)과 뿌리보다 큰 뒷부분(오른쪽 나무)으로 나눌 수 있다.따라서 귀속으로 판단하는 것이 가장 편리하다.두 개의 새로운vector를 열어 각각 뿌리보다 작은 서열과 뿌리보다 큰 서열을 저장합니다.다시 각각 두 개의 서열을 귀속시켜 후서열인지 아닌지를 판단한다.귀속을 끝내는 조건: 세그먼트의 후반부에 뿌리보다 작은 원소가 나타나면 뒷순서가 아니라false로 돌아간다.세그먼트의 앞뒤 세그먼트가 비어 있으면 이 서열은 판단을 완료하고true로 돌아갑니다.

코드

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty()) return false;
        vector<int> left;
        vector<int> right;
        int i, size=sequence.size();
        for(i=0; i<size-1; i++){
            if(sequence[i]<sequence[size-1])
                left.push_back(sequence[i]);
            else break;
        }
        for(i; i<size-1; i++){
            if(sequence[i]<sequence[size-1]) return false;
            right.push_back(sequence[i]);
        }
        if(left.empty() && !right.empty()) return VerifySquenceOfBST(right);
        if(!left.empty() && right.empty()) return VerifySquenceOfBST(left);
        if(left.empty() && right.empty()) return true;
        return VerifySquenceOfBST(left)&& VerifySquenceOfBST(right);
    }
};