二叉搜索树的后序遍历序列

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

思路

• 递归
  base_condition意味着只有一个节点或者为空，符合后序遍历顺序，返回True（注意与空树区别）。递归条件说明，如果二叉搜索树的左子树符合后序遍历，右子树也符合（即n=k-1条件满足）。那么对于根节点（n=k情况），只需要找到左右子树的分界index，并且确定分界线左边的节点值均小于根节点，右边的节点值均大于根节点即可。

代码

# -*- coding:utf-8 -*-
class Solution:def VerifySquenceOfBST(self, sequence):# write code hereif not sequence:return Falsereturn self.VerifySquenceOfBSTCore(sequence)def VerifySquenceOfBSTCore(self,sequence):if len(sequence) <= 1:return Truenode = sequence[-1]index = len(sequence) - 2while index >= 0 and sequence[index] >= node:index -= 1if index < 0:return Truefor i in range(index):if sequence[i] >= node:return False       return self.VerifySquenceOfBSTCore(sequence[:index+1]) and self.VerifySquenceOfBSTCore(sequence[index+1:-1])