二叉搜索樹的后序遍歷序列

---

輸入一個整數數組，判斷該數組是不是某二叉搜索樹的后序遍歷的結果。

如果是則返回true，否則返回false。

假設輸入的數組的任意兩個數字都互不相同。

數據范圍

數組長度 $[0,1000]$。

樣例

輸入：[4, 8, 6, 12, 16, 14, 10]輸出：true

---

算法思路 ：

1. 基本思想：

   • 利用后序遍歷特性：序列最后一個元素為根節點
   • 遞歸驗證左子樹所有節點 < 根節點 < 右子樹所有節點

2. 驗證過程：

   • 基準條件：當子序列長度 ≤ 1 時返回true
   • 劃分左右子樹：
     1. 定位第一個≥根節點的元素作為分界點
     2. 驗證右子樹部分全部＞根節點
   • 遞歸驗證：
     • 左子樹區間[l, k-1]
     • 右子樹區間[k, r-1]（排除末尾根節點）

3. 實現特點：

   • 使用類成員變量seq避免參數傳遞
   • 原地劃分不需要額外空間

復雜度類型	分析結果	說明
時間復雜度	O(n2)	最壞情況下（鏈式樹）需要n+(n-1)+…+1次比較
空間復雜度	O(n)	遞歸棧深度最大為樹高，最壞情況下（鏈式樹）為O(n)

• 最優情況（平衡二叉樹）：O(nlogn)
• 最壞情況（單支樹）：O(n2)
• 平均情況：O(nlogn)

class Solution {
public:vector<int> seq;bool verifySequenceOfBST(vector<int> sequence) {seq = sequence;return dfs(0, sequence.size() - 1);}bool dfs(int l, int r){if(l >= r) return true;int root = seq[r];int k = l;while(k < r && seq[k] < root) k ++;for(int i = k + 1; i < r; i ++){if(seq[i] < root) return false;}return dfs(l, k - 1) && dfs(k, r - 1);}
};

算法優化方向 ：

1. 單調棧解法：可優化至O(n)時間復雜度
2. 剪枝策略：當發現非法右子樹節點時立即終止遞歸
3. 迭代實現：用棧替代遞歸可優化空間復雜度為O(1)（尾遞歸優化）