1. 常规思路：递归

1.1 两个前提：

  • 首先是二叉搜索树（左子树每个节点的值 < 该节点的值 < 右子树每个节点的值）的特点；
  • 其次是后序遍历（对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身）的特点。

1.2 图解示例：

输入： [4,8,6,12,16,14,10]
返回值：true

根据上面定义我们可以画出这个二叉搜索树如下：
图片说明
可以清楚的发现根节点就是数组的最后一位，所以

  • 第一步：找到数组最后一位，即根节点root。
    紧接着
  • 第二步：获取整个数组的长度，开始遍历并与root值比较，第一个大于root的值就是左右子树的分界点。
    图片说明
  • 第三步：遍历右子树，验证是否符合二叉搜索树的概念；如上图，以12为分界点的右边所有节点都是大于root的，所以是符合二叉搜索树的。
  • 第四步：继续往下递归，查看余下的左右子树是否符合。这里再放一个不符合的数组案例给大家对比一下，数字图标表示步骤：
    图片说明

2. 核心代码

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        #先判断数组是否为空
        if not sequence:
            return False
        len_s = len(sequence) 
        root = sequence[len_s-1]   #根节点
        index = 0
        for i in range(len_s):
            if sequence[i] >= root:
                index = i #得到划分左右子树的索引位
                break
        #这里再验证如果从索引位往后的节点对应值是小于根节点的，就不符合二叉搜索树概念，返回False
        for j in range(index, len_s):
            if sequence[j] < root:
                return False
        #接下来还需要再分别判断剩余左子树、右子树是否为二叉搜索树
        #假设左子树为二叉搜索树，那么调用上面的函数就会得到如下数据：
        left = True
        if index > 0:
            left = self.VerifySquenceOfBST(sequence[0:index])
        #同理右子树
        right = True
        if index < len_s-1:
            right = self.VerifySquenceOfBST(sequence[index:-1])
        return left and right

3. 复杂度分析

  • 时间复杂度：O(图片说明 ) （递归占用 O(n)；最差情况下（当树退化为链表），每轮递归都需遍历树所有节点，占用 O(n)）
  • 空间复杂度：O(n) (最差情况下当树退化为链表，递归的深度达到n)

----------------------------------------------我是解法二的分割线-------------------------------------------------------

4. 解法二：逆序后序遍历 + 辅助栈

4.1 思路

后序遍历是“左节点 ---> 右节点 ---> 根节点”，那么逆序后序遍历就是👉：“根节点 ----> 右节点 ----> 左节点”。

按照这个思路，上面的示例(👉 [4,8,6,12,16,14,10]）我们可以这么拆解（辅助栈只存储递增的节点）：

  • 先把根节点10 添加到辅助栈 ([10])，然后遍历右子树。
  • 如果右子树存在，那么下一个数一定是 大于根节点的，且它是右子树的根节点（这里就是14），也把它添加到辅助栈中(此时为[10, 14]) ；依次类推，直到下一个数小于(这里就是12）右子树根节点，说明右子树已经遍历结束 (此时辅助栈中有[10,14,16]) 。
  • 此时的这个小于根节点的数（就是 12），并不一定是左子树的子节点。所以这里需要判断：
    • 先把刚刚压入的右子树节点都弹出栈(即弹出[14, 16])，此时栈只有一个元素(即[10])；
    • 由于栈顶元素（10）小于 12，那么最后出栈的 14 就是这个 12 的父节点，把它也压入栈中，此时栈👉[10,12]。
  • 下一个数是 6，又是小于当前栈中的栈顶元素 12，说明12没右子树；再次把[10,12]弹出栈，此时栈空。同理最后出栈的 10 就是 6的父节点！又把6 压入栈中，此时栈👉[6]。
  • 同理后面的 8 ，是比栈顶元素 6 大的，所以入栈[6, 8]，且 6是 8的根节点。
  • 最后的 4 比 [6, 8]小，所以[6, 8]依次出栈；且 4 是 6的左子节点。此时遍历结束，得到二叉搜索树如下：
    图片说明

4.2 核心代码

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        #先判断数组是否为空
        if not sequence:
            return False
        #初始化根节点为正无穷大，简化边界处理问题
        root = float('+inf')
        #辅助栈
        stack = []
        for i in range(len(sequence) -1, -1, -1):        #倒序遍历
            if sequence[i] > root:                       #说明此后序遍历序列不满足二叉搜索树定义，直接返回False
                return False
            else:
                while stack and stack[-1] > sequence[i]: #符合二叉搜索树定义的时候
                    root = stack.pop()                   #循环执行出栈，并将父节点root更新
                stack.append(sequence[i])                #当前节点入栈
        return True

4.3 复杂度分析

  • 时间复杂度：O(n) (遍历sequence的所有节点，各节点入栈和出栈均一次，所以为O(n)
  • 空间复杂度：O(n) (最差情况下，辅助栈需要存储所有的节点n，使用O(n)的空间)