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

题目

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

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

假设输入的数组的任意两个数字都互不相同。

数据范围

数组长度 。

样例

输入：[4, 8, 6, 12, 16, 14, 10]

输出：true

题解

class Solution {
public:

    vector<int> seq;

    bool verifySequenceOfBST(vector<int> sequence) {
        seq = sequence;
        return dfs(0, seq.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; k < r; ++ k)
            if (seq[k] < root)
                return false;

        // 递归处理左右子树
        return dfs(l, k - 1) && dfs(k, r - 1);

    }
};