【题目描述】

AcWing 46. 二叉搜索树的后序遍历序列

【思路】

class Solution {
    /*
    二叉搜索树：左子孩子小于根节点 
    */
    int seq[];
    public boolean verifySequenceOfBST(int [] _seq) {

        if( _seq.length == 0 ) return true;
        seq = _seq;
        return dfs(0, seq.length - 1);

    }
    public boolean dfs(int l, int r)
    {
        if( l >= r ) return true;
        int k = l, root = seq[r];
        //划分左右子树范围为[l, k - 1] [k, r - 1]
        while( k < r && seq[k] <  root ) k ++;
        //判断右子树是否合法
        for(int i = k; i < r; i ++ )
            if( seq[i] < root ) return false;

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

    }
}