题解 | #二叉搜索树的后序遍历序列#

• 单调栈

#include <climits>
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.size() == 0) return false;
        stack<int> st;
        int root = INT_MAX;
        for (int i = sequence.size() - 1; i >= 0; i--) {
            
            // 确定root节点，如果后续的节点值大于root，则表明左子树出现更大的数，不符合
            if (sequence[i] > root) return false;

            // 进入左子树的条件：sequence[i]的值小于前一项时
            while (!st.empty() && st.top() > sequence[i]) {
                root = st.top();  // 更新root节点
                st.pop();
            }
            
            st.push(sequence[i]);
        }
        return true;
    }
};

• 递归

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size() == 0) return false;
        return order(sequence, 0, sequence.size() - 1);
    }
    bool order(vector<int>& sequence, int l, int r) {
        // 剩一个节点的时候 返回 true
        if(l >= r) return true;
        int j;
        int root = sequence[r];
        // 找到左子树和右子树的分界点，j代表左子树的最后一个索引位置
        for(j = r; j >= l; j--) {
            if(sequence[j] < root){
                break;
            }
        }
        // 判断所谓的左子树中是否又不合法（不符合二叉搜索树）的元素
        for(int i = j; i >= l; i--) {
            if(sequence[i] > root) {
                return false;
            }
        }
        return order(sequence, l, j) && order(sequence, j+1, r-1);
    }
};