题目
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同.
思路
首先明白什么是二叉搜索树。
二叉搜索树，也称有序二叉树,排序二叉树，是指一棵空树或者具有下列性质的二叉树：
- 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 任意节点的左、右子树也分别为二叉查找树。
- 没有键值相等的节点。
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
