剑指Offer第23题-二叉搜索树的后序遍历序列

题目

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

思路

首先明白什么是二叉搜索树。

二叉搜索树，也称有序二叉树,排序二叉树，是指一棵空树或者具有下列性质的二叉树：

1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 任意节点的左、右子树也分别为二叉查找树。
4. 没有键值相等的节点。

image

牛客网某大牛的思路摘录如下：

BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）都是合法的后序序列。完美的递归定义 : ) 。

代码

# -*- coding:utf-8 -*-
class Solution:
    
    def judge(self, seq, l, r):
        if (l >= r): return True
        i = r
        while i > l and seq[i-1] > seq[r]: 
            i -=1
        j = i - 1
        while j >= l:
            if seq[j] > seq[r]:return False
            j -= 1
        return self.judge(seq, l, i-1) and self.judge(seq, i, r-1)
                
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return False
        return self.judge(sequence, 0, len(sequence)-1)

引用

https://www.nowcoder.com/questionTerminal/a861533d45854474ac791d90e447bafd