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

Difficulty
Medium
Tags
二叉树
二叉搜索树
单调栈
URL
https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
Star
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
     5
    / \
   2   6
  / \
 1   3
示例 1：
输入:[1,6,3,2,5]
输出:false
示例 2：
输入:[1,3,2,6,5]
输出:true
提示：
  1. 数组长度 <= 1000

法 1 二叉搜索树性质

思路
后序遍历的反向为特殊的先序遍历：root, 右子树，左子树。
再利用二叉搜索树的性质，卡住最大值最小值，即可
题解
class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        return self.helper(postorder, 0, len(postorder)-1, float("inf"), -float("inf"))
        
    def helper(self, postorder, l, r, max_val, min_val):
        if l > r:
            return True

        if postorder[r] < min_val or postorder[r] > max_val:
            return False
        
        # 找 左边 第一个小于 postorder[r] 的值， 为左子树
        i = r-1
        while i >= l and postorder[i] > postorder[r]:
            i -= 1

        left_tree = self.helper(postorder, l, i, postorder[r], min_val)
        right_tree = self.helper(postorder, i+1, r-1, max_val, postorder[r])

        return left_tree and right_tree

法 2 单调栈

思路
二叉搜索树是left < root < right的，后序遍历的顺序是left->right->root，乍一看，好像没有办法保证单调性，不过我们可以做一个变化，后序遍历的逆序是什么呢？
root->right->left
发现什么了吗？是的，这是换了一个方向的先序遍历，从root开始，先遍历右子树，再遍历左子树。怎么做到先root，然后right，最后left呢，只要我们反向遍历数组，这样我们就可以利用单调栈了。
下面说说单调递增栈的思路和用法。
翻转先序遍历又是root->right->left的，基于这样的性质和遍历方式，我们知道越往右越大，这样，就可以构造一个单调递增的栈，来记录遍历的元素。
为什么要用单调栈呢，因为往右子树遍历的过程，value是越来越大的，一旦出现了value小于栈顶元素value的时候，就表示要开始进入左子树了（如果不是，就应该继续进入右子树，否则不满足二叉搜索树的定义，不理解的请看下二叉搜索树的定义），但是这个左子树是从哪个节点开始的呢？
单调栈帮我们记录了这些节点，只要栈顶元素还比当前节点大，就表示还是右子树，要移除，因为我们要找到这个左孩子节点直接连接的父节点，也就是找到这个子树的根，只要栈顶元素还大于当前节点，就要一直弹出，直到栈顶元素小于节点，或者栈为空。栈顶的上一个元素就是子树节点的根。
接下来，数组继续往前遍历，之后的左子树的每个节点，都要比子树的根要小，才能满足二叉搜索树，否则就不是二叉搜索树。
题解
class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        stack = []
        prev = float("inf")
        
        # 逆向遍历，就是翻转的先序遍历
        for i in range(len(postorder)-1, -1, -1):
            # 左子树元素必须要小于递增栈被peek访问的元素，否则就不是二叉搜索树
            if postorder[i] > prev:
                return False

            # 数组元素小于单调栈的元素了，表示往左子树走了，记录下上个根节点
            # 找到这个左子树对应的根节点，之前右子树全部弹出，不再记录，因为不可能在往根节点的右子树走了
            while stack and postorder[i] < postorder[stack[-1]]:
                prev = postorder[stack.pop()]

            stack.append(i)


        return True