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

输入一个整数数组二叉排序树 遍历，以确定该数组是否是遍历二叉搜索树的结果. 如果是，则输出“是”，否则输出“否”. 假设输入数组中的任何两个数字互不相同.

想法: 二叉树遍历递归

二进制搜索树示例:

结合图中的分析:

后遍历为左，右根: [3、4、9、5、12、11、10]，与图组合二叉排序树 遍历，然后分析从左到右的后继序列，并分析子树，您可以找到:

[12] 11

发现对于每个子树，其根节点始终对应于子树的子序列序列的最后一个数字

因此，您只需要不断确定左子树间隔和右子树间隔，并判断: 左子树间隔的所有节点值<根节点值<右子树间隔的所有节点值，满足这个条件

递归方法在每一层的遍历成本为O（n），对于二叉树，递归层的平均数量为O（logn），因此递归方法的最终复杂度为O（n * logn ）

Python实现:

#-*-编码: utf-8-*-

类解决方案:

def VerifySquenceOfBST（自身，序列）:

#在此处编写代码

length = len（序列）

如果长度== 0:

返回错误

如果长度== 1:

返回True

root =序列[-1]

左= 0

while序列[左]

左+ = 1

对于范围内的j（左侧，长度-1）:

如果序列[j]

返回错误

返回self.VerifySquenceOfBST（序列[: 左]）或self.VerifySquenceOfBST（序列[左: 长度-1]）

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-212672-1.html