剑指33：二叉搜索树的后序遍历序列

传送门

nowcoder
leetcode

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
如果是则返回 true，否则返回 false。
假设输入的数组的任意两个数字都互不相同。

C++ 代码 - nowcoder

/*
    递归实现
*/
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.empty()) return false;
        if (sequence.size() == 1) return true;
        return VerifySquenceOfBSTCore(sequence, 0, sequence.size() - 1);
    }

    bool VerifySquenceOfBSTCore(vector<int>& sequence, int start, int end) {
        if (start >= end) return true;

        int idx = start;
        while (idx < end && sequence[idx] < sequence[end]) idx ++;
        // 二叉搜索树，找到第一个大于根的元素，它之前都是左子树，之后都是右子树。
        for (int i = idx; i < end; i ++) {
            if (sequence[i] < sequence[end]) return false; // 右子树必须全部大于根，否则就是假
        }

        return VerifySquenceOfBSTCore(sequence, start, idx - 1)
            && VerifySquenceOfBSTCore(sequence, idx, end - 1);
    }
};

C++ 代码 - leetcode

class Solution {
public:
    bool verifyTreeOrder(vector<int>& postorder) {
        if (postorder.empty() || postorder.size() == 1) return true;
        return dfs(postorder, 0, postorder.size() - 1);
    }

    bool dfs(vector<int>& postorder, int start, int end) {
        if (start >= end) return true;

        // 二叉搜索树的左子树都小于根，找到第一个大于根的元素
        int idx = start;
        while (idx < end && postorder[idx] < postorder[end]) {
            idx ++;
        }

        // 二叉搜索树的右子树都大于根 
        for (int i = idx; i < end; i ++) {
            if (postorder[i] <= postorder[end]) {
                return false;
            }
        }

        return dfs(postorder, start, idx - 1)
            && dfs(postorder, idx, end - 1);
    }
};