[数据结构与算法]剑指Offer 33. 二叉搜索树的后序遍历序列(划分左右子树递归)

题目：

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

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

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

解题思路：

在二叉搜索树中，左子树的元素必小于根，右子树的元素必大于根。所以从头开始遍历知道第一个比根节点大的元素为止，以此来划分左右子树。若所有的子树都正确，则此序列为二叉搜索树的后序遍历。

划分时，左子树的元素必小于根，则只需判断右子树是否全部比根节点大即可，如果不满足则结束，满足的话就递归。

代码：

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        #二叉搜索树的性质：
        #如果左子树不空，左子树的所有节点的值小于根节点的值。
        #如果右子树不空，则右子树所有节点的值大于跟节点的值。
        if postorder == []:return True
        n = len(postorder)
        for i in range(n):
            if postorder[i] > postorder[-1]:
                break
        left_tree = postorder[:i]
        right_tree = postorder[i:n-1]

        for num in right_tree:
            if num < postorder[-1]:
                return False
        return self.verifyPostorder(left_tree) and self.verifyPostorder(right_tree) 
        #判断左子树是否正确和右子树是否正确

复杂度：

• 时间复杂度：O(N^2)，递归占用O(N),最差情况下（当树退化为链表），每轮递归都需遍历树所有节点，占用O(N)
• 空间复杂度：O(N)，最差情况下，递归深度将达到N