问题

判断一个后序遍历是否为BST的后序遍历

算法：DFS

经典题。后序遍历的最后一个节点是根节点，BST根节点左边应当小于根节点，右边大于根节点。若判断左右子树合法后递归即可。

时间复杂度

$O(N^2)$, 当树退化为链表时达到最坏复杂度

代码

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        return dfs(0, postorder.size()-1, postorder);
    }

    bool dfs(int l, int r, vector<int> &postorder){
        if(l >= r){
            return true;
        }
        int root = postorder[r];
        int k;
        for(k = l; k < r; k ++){
            if(postorder[k] >= root) break;
        }
        int t = k;
        while(t < r){
            if(postorder[t] < root) return false;
            t ++;
        }

        return dfs(l, k-1, postorder) && dfs(k, r-1, postorder);
    }
};