去哪儿第二题BST判定

#include <iostream>
#include <map>
#include <vector>
#include <stack>
using namespace std;

// 判断序列是否为BST的后续遍历序列
bool verifySeqOfBST(int A[], int len) {
    if (A == NULL || len <1)
        return false;
    int root = A[len - 1];

    int i = 0;
    for (; i < len - 1; ++i) {
        if (A[i] > root)
            break;
    }

    int j = i;
    for (; j < len - 1; ++j) {
        if (A[j] < root)
            return false;
    }

    bool left = true;
    if (i > 0)
        left = verifySeqOfBST(A, i);

    bool right = true;
    if (i < len - 1)
        right = verifySeqOfBST(A + i, len - i - 1);

    return (left&&right);

}

// 得到 根左右 序列
void getRrlList(map<int, vector<int>> m, int rootVal, stack<int>& s) {
    vector<int> childrenVec = m[rootVal];
    int left = childrenVec[0];
    int right = childrenVec[1];

    if (rootVal != -1)
        s.push(rootVal);

    if (right != -1) {
        getRrlList(m, right, s);
    }

    if (left != -1) {
        getRrlList(m, left, s);
    }
}

int main() {

    int rootVal;

    cin >> rootVal;

    map<int, vector<int>> m;

    // 输入二叉树的结构
    int root, left, right;
    while (scanf("%d:%d|%d", &root, &left, &right) != EOF) {
        m[root].push_back(left);
        m[root].push_back(right);
    }

    stack<int> s;
    getRrlList(m, rootVal, s);

    const int len = s.size();
    vector<int> cols;
    while (!s.empty()) {
        int tmp = s.top();
        s.pop();
        cols.push_back(tmp);
    }

    int* A = new int[len];

    for (int i = 0; i < cols.size(); ++i) {
        A[i] = cols[i];
    }


    bool isBST = verifySeqOfBST(A, cols.size());

    if (isBST)
        cout << 1 << endl;
    else
        cout << 0 << endl;
    delete[] A;

    return 0;
}