判断是否为二叉搜索树的后序遍历序列

简介: 二叉树相关练习

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


题目链接:二叉搜索树的后序遍历序列_牛客题霸_牛客网


知识点:

二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树


二叉排序树或者是一棵空树,或者是具有下列性质的二叉树

(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;

(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;

(3)左、右子树也分别为二叉排序树;

(4)没有键值相等的节点。


而且这里题目也强调了第四点,任意两个数字都不同,也就是没有键值相等的点。


分析:


已知条件:后序序列最后一个值为root;二叉搜索树左子树值都比root小,右子树值都比root大。

1、确定root;

2、遍历序列(除去root结点),找到第一个大于root的位置,则该位置左边为左子树,右边为右子树;

3、遍历右子树,若发现有小于root的值,则直接返回false;(不用再去遍历左子树确认是否有大于root的值,因为上一步找到第一个大于root值的位置的时候,就已经确认了左边一定全部小于root)

4、分别判断左子树和右子树是否仍是二叉搜索树(即递归步骤1、2、3)。


AC代码:

publicclassSolution {
publicbooleanVerifySquenceOfBST(int [] sequence) {
if (sequence==null||sequence.length==0)    returnfalse;
returnVertify1(sequence, 0, sequence.length-1);
    }
privatebooleanVertify1(int[] a, intstart, intend) {
if (start>=end)    returntrue; // 截止条件可用[4,6,7,5]数据测试inti=start;
while (a[i] <a[end]) {
++i;
        }
for (intj=i; j<end; ++j) {
if (a[j] <a[end])    returnfalse;
        }
returnVertify1(a, start, i-1) &&Vertify1(a, i, end-1);
    }
}

image.gif


================Talk is cheap, show me the code===================

目录
打赏
0
0
0
0
128
分享
相关文章
[Hive]Lateral View使用指南
1. 语法 lateralView: LATERAL VIEW udtf(expression) tableAlias AS columnAlias (',' columnAlias)* fromClause: FROM baseTable (lateralView)* 2. 描述 Lateral View一般与用户自定义表生成函数(如explode())结合使用。
4620 0
ChatGPT模型采样算法详解
采样算法对ChatGPT的文本生成质量至关重要。本文重点讲解ChatGPT中temperature和top_p的采样原理,以及它们对模型输出的影响。帮助大家生成更灵活生动的内容。
1728 0
ChatGPT模型采样算法详解
|
8月前
|
Spring高手之路19——Spring AOP注解指南
在本文中,我们将深入探索Spring AOP(面向切面编程)的核心概念及其在现代Spring应用中的实际应用。从基本的注解使用到复杂的切面配置,本文将一步步指导你如何利用Spring AOP提升代码的模块化,帮助你在Spring开发路上更进一步。
103 3
Spring高手之路19——Spring AOP注解指南
Spring高手之路6——Bean生命周期的扩展点:BeanPostProcessor
在本篇文章中,我们将深入探讨Spring框架中的重要组件——BeanPostProcessor。首先,我们将了解其设计理念和目标,然后通过实际的例子学习如何基础使用它,如何通过BeanPostProcessor改变Bean的初始化结果以及如何利用它修改Bean的属性。最后,我们将深入理解后置处理器在Bean生命周期中的作用和执行时机,帮助读者更好地理解和使用这个强大的工具。
145 1
Spring高手之路6——Bean生命周期的扩展点:BeanPostProcessor
如何把其他代码托管平台git仓库迁移到github还保留历史日志记录?图解步骤,值得收藏!
我在其他的代码托管平台(不是github)有一套代码,不同代码托管平台之间没有相互迁移的功能,怎么将仓库代码提交到github仓库呢?我会讲解适合于所有不同托管平台Git仓库之间的迁移方法,所以就不要老是抱怨着为什么没有外部仓库迁移过来的功能了。
344 0
如何把其他代码托管平台git仓库迁移到github还保留历史日志记录?图解步骤,值得收藏!
数据库如何实现读写分离以应对高并发?
【6月更文挑战第17天】数据库如何实现读写分离以应对高并发?
120 1
Spring高手之路7——事件机制与监听器的全面探索
本篇文章为你详细解析了Spring的事件机制,包括了Spring事件模型的四个核心概念:事件源、事件、广播器、监听器。我们通过深入浅出的实例解析了如何自定义事件和监听器,以及如何在实际项目中应用。最后,我们还详细探讨了监听器和Bean的生命周期的关系。无论你是Spring初学者,还是有一定经验的开发者,阅读本文都将帮助你更深入地理解Spring的事件机制和监听器,掌握Spring框架的核心技术。
1339 0
Spring高手之路7——事件机制与监听器的全面探索
RocketMQ:揭秘电商巨头背后的消息队列秘密
**RocketMQ概览:**高性能分布式消息队列,适用于有序消息、事务处理、流计算、消息推送、日志处理及Binlog分发。在双11等高流量场景下证明了其性能、稳定性和低延迟。Java开发,利于扩展,性能超RabbitMQ,支持死信队列,但可能有集成兼容性问题。适合Java开发者,为电商等场景优化,每秒处理大量消息。
85 3
RocketMQ:揭秘电商巨头背后的消息队列秘密

热门文章

最新文章