c++ - 判断二叉搜索树的后序是否有效

Question

这是我的代码，有三个测试用例，但我只通过了其中两个。而且我不知道代码有什么问题。请帮我！

#include <cstdio>

int isValid(int a[], int low, int high) {
    if (low >= high)
        return 1;

    int root = a[high];
    int i = 0;
    while (a[i] < root && i < high)
        i++;
    // i == low, the left child is null
    // i == high, the right child is null
    if (a[i - 1] < root && root < a[high - 1] 
        || i == low && root < a[high - 1] || a[i - 1] < root && i == high) {
        return isValid(a, low, i - 1) && isValid(a, i, high - 1);
    } else {
        return 0;
    }
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        int a[n];
        for (int i = 0; i < n; ++i)
            scanf("%d", &a[i]);

        if (isValid(a, 0, n - 1)) {
            printf("Yes\n");
        } else {
            printf("No\n");     
        }
    }
    return 0;
}

样本输入：

7

5 7 6 9 11 10 8

4

7 4 6 5

样本输出：

Yes

No

Answer 1

Inorder could guarantee the nondecreasing order for BST, but poster-order can't. And you can't deduce the original binary tree from the poster-order sequence. Take an instance, 5 7 6 could be valid full BST also could be invalid BST.