劍指 offer acwing 46 二叉搜尋樹的後序周遊序列

題面

題解

對于二叉搜尋樹，我們知道，左子樹的值都小于根節點，右子樹的值都大于根節點，給出後序周遊，最後一個節點一定是根節點，然後從前向後，隻要是小于根節點的點都是左子樹中的，從前向後找第一個大于根節點的位置，就是右子樹的開始，然後遞歸處理左右子樹，看是否合法

代碼

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