c++ - 二分探索木のポストオーダーが正しいかどうかを判定する

Question

これが私のコードです。3 つのテスト ケースがありますが、合格したのは 2 つだけです。そして、コードの何が問題なのかわかりません。私を助けてください！

#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 は BST の非減少順序を保証できますが、poster-order は保証できません。また、ポスター順シーケンスから元のバイナリ ツリーを推測することはできません。たとえば、5 7 6 は有効なフル BST である可能性があり、無効な BST である可能性もあります。