【剑指offer】33. 二叉搜索树的后序遍历序列

一、题目描述

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

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

示例 1：

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

示例 2：

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

提示：

数组长度 <= 1000

二、解题思路 & 代码

2.1 分治 + 递归

后续遍历：左-右-root
所以核心思想就是：

把 root 先找出来
遍历，并和 root 对比，找到左子树和右子树的边界
递归求解

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        if not postorder or len(postorder) == 1:
            return True
        root = postorder[-1]
        index = 0
        for i in range(len(postorder)):
            if postorder[i] >= root:
                index = i
                break
        left = postorder[: index]
        right = postorder[index: -1]  # 去掉最后一个 root
        for num in right:
            if num < root:
                return False
        return self.verifyPostorder(left) and self.verifyPostorder(right)

复杂度分析：

时间复杂度 $O(N^2)$ ：每次递归的时候减去一个根节点，因此递归占用 $O (N)$ ；最差情况下（即当树退化为链表），每轮递归都需遍历树所有节点，占用 $O (N)$ 。
空间复杂度 $O (N)$ ：最差情况下（即当树退化为链表），递归深度将达到 N 。

2.2 辅助单调栈

参考：LeetCode优秀题解

class Solution:
    def verifyPostorder(self, postorder: [int]) -> bool:
        stack, root = [], float("+inf")
        for i in range(len(postorder) - 1, -1, -1):
            if postorder[i] > root: return False
            while(stack and postorder[i] < stack[-1]):
                root = stack.pop()
            stack.append(postorder[i])
        return True

复杂度分析：

时间复杂度 $O (N)$ ：遍历 $p o s t o r d e r$ 所有节点，各节点均入栈 / 出栈一次，使用 $O (N)$ 时间。
空间复杂度 $O (N)$ ：最差情况下，单调栈 $s t a c k$ 存储所有节点，使用 $O (N)$ 额外空间。

参考：

LeetCode优秀题解