二叉搜索树的后序遍历序列
题目
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
方法
二叉搜索树的后序遍历顺序是：(postorder of left branch) (postorder of right branch) root
可以观察到后序序列sequence[-1]是根结点root，已知二叉搜索树中任意两个数字不相同，即根结点的数值大于左子树上所有结点的数值，小于右子树上所有结点的数值。
通过遍历，可以将第一个大于root的左边部分划分为左子树，第一个大于root的到root之前的右侧部分划分为右子树。再递归调用主函数去检验左右子树是否是二叉搜索树。这样可以保障左边部分都比根结点小，但不能保证右边部分都大于根结点，所以需要对右边部分进行检验。
需要注意的地方，当序列为空，即二叉搜索树是空树，认为是False。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
# postorder: (postorder of left branch) (postorder of right branch) root
length=len(sequence)
if length==0:
return False
elif length==1:
return True
root=sequence[-1]
for i in range(length):
if sequence[i]>root:
break
for j in range(i,length-1):
if sequence[j]<root:
return False
# 当左右分支的数据长度为0，即证明左右分支是正确的后序遍历，应当直接返回True
left,left_nums=True,sequence[:i]
right,right_nums=True,sequence[i:length-1]
if len(left_nums)>0:
left=self.VerifySquenceOfBST(left_nums)
if len(right_nums)>0:
right=self.VerifySquenceOfBST(right_nums)
return left and right