本题来自《剑指offer》 二叉搜索树的后序遍历序列
题目：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路：
对二叉搜索树有个明确的概率，即左节点小于根节点，右节点大于根节点。
后序遍历是左友根遍历。
首先找到根节点，那么根节点左序列为左子树，右序列为右子树。以此递归。
Python Code：
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
if not sequence: #边界条件
return False
return self.VerifyBST(sequence) #调用二叉搜索树验证程序
def VerifyBST(self,sequence):
if not sequence: #如果切割到最后为空，则说明为True
return True
root = sequence.pop() #最后一个元素是根节点
index = self.FindIndex(sequence,root) #找到下标，即左子树小于根节点，右子树大于根节点
if self.VerifyRight(sequence[index:],root):
left = sequence[:index] #分割此中间值下，左子树为从头到下标
right = sequence[index:] #分割从中间值到末尾
return self.VerifyBST(left) and self.VerifyBST(right) #分别对左右子树递归进行遍历
return False
def VerifyRight(self,sequence,target): #验证该序列中的元素与目标值的关系
if not sequence:
return True
return min(sequence) > target #返回真假，如果最下的值大于目标返回真，否则返回假
def FindIndex(self,sequence,target): #给定一个数组，返回元素的下标
for i ,num in enumerate(sequence): #枚举全部的元素，包括下标和元素值
if num > target: #直到大于目标值的即可
return i
return len(sequence) #如果没有找到，那么就是最后一个元素
总结：
明确定义，画图，手动推理找规律。