劍指Offer：判斷二叉搜索樹的後序遍歷序列（九度OJ 1367）

題目描述

給定一個整數數組，判斷該數組是否為某二叉搜索樹的後序遍歷結果。若是輸出 Yes，否則輸出 No。假設數組中任意兩數互不相同。

輸入輸出

• 每個測試用例兩行：第一行 n（1 ≤ n ≤ 10000），第二行 n 個整數
• 輸出 Yes 或 No

樣例

輸入：
7
5 7 6 9 11 10 8
4
7 4 6 5

輸出：
Yes
No

核心原理

二叉搜索樹（BST）性質：左子樹所有節點 < 根節點 < 右子樹所有節點。
後序遍歷順序：左子樹 → 右子樹 → 根節點。

因此，後序序列的最後一個元素必是根節點。剩餘序列可分為兩段：
前段（左子樹）全部 < 根值，後段（右子樹）全部 > 根值。遞歸驗證即可。

算法流程

1. 取序列最後一個元素 root = seq[j] 作為根
2. 從右向左找到第一個 < root 的位置 flag，此前應全為 > root（右子樹）
3. 從 flag 向左驗證是否全為 < root（左子樹）
4. 若分割點不符合預期（即存在交叉），返回 0
5. 遞歸驗證左子序列 [i, flag] 和右子序列 [flag+1, j-1]

特殊情況處理

BST 可能只有左子樹或只有右子樹（非滿二叉樹）。例如序列 1 2 3（只有右子樹）或 3 2 1（只有左子樹）均合法。代碼中通過以下判斷處理：

if (test[i] > test[j] || test[j-1] < test[j]) {
    // 單邊子樹：全部大於根 或 全部小於根
    return isPost(i, j-1);
}

完整代碼

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

int test[10005] = {0};

int isPost(int i, int j);

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++) scanf("%d", &test[i]);
        if (isPost(0, n-1)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

int isPost(int i, int j) {
    if (i == j) return 1;  // 單節點
    
    int k = j - 1;
    // 從右向左找右子樹邊界（全 > root）
    while (k >= i && test[k] > test[j]) k--;
    int flag = k;
    // 繼續向左驗證左子樹（全 < root）
    while (k >= i && test[k] < test[j]) k--;
    
    if (k == i - 1) {  // 完美分割
        // 單邊子樹優化
        if (test[i] > test[j] || test[j-1] < test[j]) {
            return isPost(i, j-1);
        } else {
            return isPost(i, flag) && isPost(flag+1, j-1);
        }
    } else {
        return 0;  // 存在交叉，非BST後序
    }
}

/**************************************************************
 Problem: 1367
 Result: Accepted
 Time: 10 ms
 Memory: 952 kb
 **************************************************************/

複雜度分析

• 時間複雜度：最壞 O(n²)（退化鏈狀樹），平均 O(n log n)
• 空間複雜度：O(h) 遞歸棧空間