Leetcode题解剑指 Offer 33. 二叉搜索树的后序遍历序列

PROBLEM

难度中等

MY ANSWER

后序遍历序列最后一个元素为根节点，由二叉搜索树性质可得，序列以第一个比根节点值大的元素为界，左边全部小于根节点值，右边全部大于根节点值，可以通过检查是否符合该情况来判断能否满足二叉搜索树的定义。递归对数组进行遍历，先遍历整个树判断是否符合上述条件，然后是左子树、右子树如此递归。时间复杂度为O(n^2)，空间复杂度O(n)。

class Solution {
public:
    vector<int> p;
    bool judge(int left, int right){
        // cout<<left<<right<<endl;
        if(left >= right - 1) {
            return true;
        }
        int sign = p[right];
        int mid = right;
        for(int i = left; i < right; i++) {
            if(p[i] > sign) {
                mid = i;
                break;
            }
        }
        // cout<<mid<<endl;
        // int res = judge(left, mid - 1) && judge(mid, right - 1);
        for(int i = mid; i < right; i++) {
            if(p[i] < sign) {
                return false;
            }
        }
        return judge(left, mid - 1) && judge(mid, right - 1);
    }
    bool verifyPostorder(vector<int>& postorder) {
        p = postorder;
        return judge(0, p.size() - 1);
    }
};

BETTER SOLUTION

基本思想为遍历后序遍历序列的倒序，若出现降序的节点，则该节点的父节点为节点前面升序序列的第一个比它大的节点，且节点右边的所有节点值都应该小于父节点值。

使用单调栈来辅助构造二叉树，root表示父节点值。从末尾往前遍历序列，若值大于root，说明不满足二叉搜索树定义返回false；若栈不为空且值小于栈顶，则将栈顶值赋值给root并出栈，直到栈顶值小于当前值，最后将当前值入栈。若遍历完成，则说明满足二叉搜索树定义返回true。时间复杂度为O(n)，空间复杂度O(n)。

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        stack<int> s;
        int root = INT_MAX;
        for(int i = postorder.size() - 1; i >= 0; i--) {
            if(postorder[i] > root) {
                return false;
            }
            while(s.size() && s.top() > postorder[i]) {
                root = s.top();
                s.pop();
            }
            s.push(postorder[i]);
        }
        return true;
    }
};

SUMMARY

重点掌握单调栈在此题中的应用。