검지 Offer 알고리즘 구현의 24: 두 갈래 검색 트리의 후속 반복 시퀀스

제목: 정수 그룹을 입력하여 이 그룹이 어떤 두 갈래 검색수의 후속 역행 결과인지 판단합니다.만약 그렇다면true를 되돌려주고, 그렇지 않으면false를 되돌려줍니다.만약 입력한 수조의 임의의 두 수조가 서로 다르다면
생각:
마지막 요소는 루트입니다.BST의 특징은 왼쪽 트리의 모든 노드가 루트보다 작고 오른쪽 트리의 모든 노드가 루트보다 크다는 것이다.귀착, 왼쪽 트리일 수도 있는 서열을 찾았고, 나머지는 오른쪽 트리일 수도 있는 서열을 찾았습니다.후보의 오른쪽 트리 서열이 루트보다 큰 조건을 충족하는지 판정합니다.만약 만족한다면 좌우 자수 판단에 귀속된다
컴파일 환경: ArchLinux+Clang3.3, C++11
구현 1:

#include <iostream>
#include <cassert>
using namespace std;

bool checkSeqOfBST(int *seq, int len)
{
    if (!seq || len < 1) return false;
    int root = seq[len - 1];
    int *ptr = seq;
    int *end = seq + len - 1; // excluding
    while (ptr < end && *ptr <= root) ptr++; //  [seq, end),  ，ptr ( )
    int leftLen = ptr - seq;
    while (ptr < end) { //  [ptr, end)， 
        if (*ptr < root)
            return false;
        ptr++;
    }
    bool left = leftLen > 0
                ? true
                : checkSeqOfBST(seq, leftLen); //  
    bool right = len - leftLen - 1 > 0
                ? true
                : checkSeqOfBST(seq+leftLen, len - 1 - leftLen); //  
    return left && right;
}

int main()
{
    int a[] {5,7,6,9,11,10,8};
    int b[] {7,4,6,5};
    assert(checkSeqOfBST(a, sizeof(a)/sizeof(int)));
    assert(!checkSeqOfBST(b, sizeof(b)/sizeof(int)));
}