题目描述

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

参考以下这颗二叉搜索树：

 5
/  \

2 6
/ \
1 3
示例 1：

输入: [1,6,3,2,5]
输出: false
示例 2：

输入: [1,3,2,6,5]
输出: true

提示：

数组长度 <= 1000

题解

题目给定一个后序遍历的数组，要求我们判断这个数组是否能组成一个后序遍历的二叉树。
后序遍历我们首先想到他的遍历顺序是左右根，我们可以借用分治的思想，将这个问题划分成一个个小问题。 首先我们可以解决 [left,right]这个数组是否满足二叉搜索树

• 若left >= right,说明区间只有一个元素或者空，这个时候它满足二叉搜索树的定义，所以是二叉搜索树。
• 但若像【1,3,2,6,5】，我们可以知道5肯定是这颗子树的根，只需要定位右区间的位置，通过end指针寻找比root大的节点，然后我们定位到2元素的下标，设置该位置为mid，那么左区间就是【1，3，2】，右区间就是【2，6】，判断左区间是否小于root，若满足，说明5为根的是没有问题的。
• 紧接着我们需要判断以6为根，以2为根，当每一个子区间都满足如上的定义，说明数组可以构建一颗搜索二叉树。

最差情况下是单链表的形式。
时间复杂度 O(N^2)
空间复杂度 O(N) ： 最差情况下（即当树退化为链表），递归深度将达到 O（N） 。

class Solution {
public:
    //需要抓住一点：后序遍历的结果是
    //左右跟，说明了从后往前遍历的时候，知道遍历的结果比root小，才结束了右子树。
    bool _verifyPostorder(int left, int right, vector<int>& postorder)
    {
        if (left >= right)
            return true;//区间只有一个节点，说明一定满足二叉搜索树的定义
        int rootVal = postorder[right];
        int end = right - 1;//划分左右区间
        //需要注意无右子树，无左子树的情况
        while (end >= left && postorder[end] > rootVal) end--;
        int mid = end;
        //划分区间 [left,mid] [mid + 1,right]

        //这里是判断 左子树不能大于跟
        while (end >= left && postorder[end] < rootVal) end--;
        //若end 没走到-1，说明这里出现了左子树的节点大于跟，不满足二叉搜索树
        if (end >= left) return false;

        return _verifyPostorder(left, mid, postorder)
            && _verifyPostorder(mid + 1, right - 1, postorder);
    }
    bool verifyPostorder(vector<int> postorder) {
        return _verifyPostorder(0, postorder.size() - 1, postorder);
    }
};

单调栈

由于后序遍历是左右根，那么当我们从后往前遍历，说明顺序变为根右左。到从 n-1,遍历到n-2，有如下情况。期间我们会root维护根节点。
初始化root 为INT_MAX，相当于我们一开始会先入最右列节点。相当于下图绿色标出的节点会先入队列，往后入节点会更新root，一开始是靠下的绿色节点作为root，

绿色为root的顺序，红色为访问节点的顺序。

• 若postorder[i] > 栈顶元素，若postorder[i] 大于root，那么说明当前节点是左子树，但是大于根节点，不满足；若小于root，则入栈即可。
• 若postorder[i] < 栈顶元素,说明当前元素不是root的右子树了，此时将栈顶元素大于postorder[i]都弹出，表明这个节点是最新栈顶的左孩子。

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        //单调栈 -- 逆序遍历  根右左
        //每次遍历到子树的时候都是先遍历到跟
        stack<int> st;
        int root = INT_MAX;
        for(int i = postorder.size() - 1;i >= 0; --i)
        {
            //栈存储的是root的右子树，遍历到postorder[i]的时候出掉部分/全部 栈的节点
            //就可以找到i节点在哪个节点的左子树，并且更新root
            //1.当root确定的时候，遍历i节点的时候若大于root，说明左子树中出现大于root，不满足二叉搜索树
            //2.一开始设置root为INT_MAX，相当于设置了一个dummy节点，让跟节点可以先入栈
            if(postorder[i] > root)
            {
                return false;
            }
            //这个时候相当于遍历root的左子树
            while(!st.empty() && postorder[i] < st.top())
            {
                //寻找最近的根节点
                root = st.top();
                st.pop();
            }
            st.push(postorder[i]);
        }
        return true;
    }
};

end

• 喜欢就收藏
• 认同就点赞
• 支持就关注
• 疑问就评论