剑指offer之023-二叉搜索树的后序遍历序列

题目描述

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

思路

二叉搜索树有:

  • 结点值:左<根<右
  • 左右子树都是搜索树

后序遍历顺序为:左->右->根

  • 最后一个数为根结点,通过根节点值切割左右子树。
  • 判断左右子树是否二叉搜索树

对于[4,8,6,12,16,14,10]

    10
 6     14  
4 8  12   16
def helper(sequence):
    if len(sequence) <= 1: return True
    root = sequence[-1]
    for i in range(len(sequence)):
        if sequence[i] > root:
            break
    for j in range(i, len(sequence)-1):
        if sequence[j] < root:
            return False
    return helper(sequence[:i]) and helper(sequence[i:-1])


def VerifySquenceOfBST(sequence):
    # write code here
    if not sequence: return False
    return helper(sequence)
print(VerifySquenceOfBST([7,4,6,5]))

关于明柳梦少

坚守自己的原则,不随波逐流。