一、题目描述

JZ23 二叉搜索树的后序遍历序列
题目大意：输入一个序列, 判断它是不是某二叉搜索树的后序遍历结果
注意审题：假设输入序列的任意两个数字都互不相同且空树不是二叉搜索树

二、算法1（分治）

解题思路

  1. 二叉树的后序遍历顺序是：左子树 -> 右子树 -> 根节点
  2. 因此序列的最后一个数代表了根节点
  1. 因此我们可以将一个序列划分为3段, 左子树+右子树+根, 例如[4, 8, 6, 12, 16, 14, 10]可以根据根节点的值将其划分为左子树[4, 8, 6], 右子树[12, 16, 14], 根[10], 由于我们是先确定的右子树区间, 因此当左子树区间中出现大于根节点的值时, 序列不合法, 我们再采用分治的思想, 对于每段序列代表的子树, 检查它的左子树和右子树, 当且仅当左右子树都合法时返回true

代码实现 

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        n = len(sequence)
        if n == 0:
            return False
        return self.check(sequence,0,n-1)
    def check(self, seq, left, right):
        if left >=right:
            return True
        root = seq[right]
        j = right-1
        while j>=0 and seq[j] >root:
            j-=1
        for i in range(left,j+1):
            if seq[i] >root:
                return False
        return self.check(seq, left, j) and self.check(seq, j+1,right-1)
        

时间复杂度：O(n^2), n为二叉树节点的个数, 当树为链式时时间复杂度最坏为O(n^2)
空间复杂度：O(n), 当树为链式结构时, 递归深度为n

三、算法2（栈）

解题思路

  1. 实际上二叉树的中序遍历和后序遍历对应着一种栈的压入、弹出序列, 而对后序遍历序列从小到大排序就得到了中序遍历序列
  2. 我们得到中序遍历序列后, 将其作为入栈序列, 检查后序遍历序列是不是一个合法的出栈序列即可
  3. 对于检查栈的合法压入、弹出序列问题, 请看栈的压入、弹出序列题解

代码实现 

class Solution:
    def IsPopOrder(self, pushV, popV):
        n = len(pushV)
        stk = []
        i,j=0,0
        while i < n:
            stk.append(pushV[i])
            while len(stk) !=0 and stk[-1] == popV[j]:
                j+=1
                stk.pop()
            i += 1
        return j == n
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if len(sequence) == 0:
            return False
        inorder = sorted(sequence)
        return self.IsPopOrder(inorder,sequence)
时间复杂度：O(nlogn), 时间复杂度取决于排序
空间复杂度：O(n), 额外数组和辅助栈的空间

参考资料：