题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路
二叉搜索树有：
- 结点值:左<根<右
- 左右子树都是搜索树
后序遍历顺序为：左->右->根
- 最后一个数为根结点，通过根节点值切割左右子树。
- 判断左右子树是否二叉搜索树
对于[4,8,6,12,16,14,10]
10
6 14
4 8 12 16def 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]))