当前位置: 首页 > news >正文

面试算法53:二叉搜索树的下一个节点

题目

给定一棵二叉搜索树和它的一个节点p,请找出按中序遍历的顺序该节点p的下一个节点。假设二叉搜索树中节点的值都是唯一的。例如,在图8.9的二叉搜索树中,节点8的下一个节点是节点9,节点11的下一个节点是null。
在这里插入图片描述

分析:时间复杂度O(n)的解法

解决这个问题的最直观的思路就是采用二叉树的中序遍历。可以用一个布尔变量found来记录已经遍历到节点p。该变量初始化为false,遍历到节点p就将它设为true。在这个变量变成true之后遍历到的第1个节点就是要找的节点。

解:时间复杂度O(n)的解法

public class Test {public static void main(String[] args) {TreeNode node1 = new TreeNode(1);TreeNode node2 = new TreeNode(2);TreeNode node3 = new TreeNode(3);TreeNode node4 = new TreeNode(4);TreeNode node5 = new TreeNode(5);TreeNode node6 = new TreeNode(6);node4.left = node2;node4.right = node5;node2.left = node1;node2.right = node3;node5.right = node6;TreeNode result = inorderSuccessor(node4, node5);System.out.println(result);}public static TreeNode inorderSuccessor(TreeNode root, TreeNode p) {Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;boolean found = false;while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);cur = cur.left;}cur = stack.pop();if (found) {break;}else if (p == cur) {found = true;}cur = cur.right;}return cur;}
}

分析: 时间复杂度O(h)的解法

下面按照在二叉搜索树中根据节点的值查找节点的思路来分析。从根节点开始,每到达一个节点就比较根节点的值和节点p的值。如果当前节点的值小于或等于节点p的值,那么节点p的下一个节点应该在它的右子树。如果当前节点的值大于节点p的值,那么当前节点有可能是它的下一个节点。此时当前节点的值比节点p的值大,但节点p的下一个节点是所有比它大的节点中值最小的一个,因此接下来前往当前节点的左子树,确定是否能找到值更小但仍然大于节点p的值的节点。重复这样的比较,直至找到最后一个大于节点p的值的节点,就是节点p的下一个节点。

解:时间复杂度O(h)的解法

public class Test {public static void main(String[] args) {TreeNode node1 = new TreeNode(1);TreeNode node2 = new TreeNode(2);TreeNode node3 = new TreeNode(3);TreeNode node4 = new TreeNode(4);TreeNode node5 = new TreeNode(5);TreeNode node6 = new TreeNode(6);node4.left = node2;node4.right = node5;node2.left = node1;node2.right = node3;node5.right = node6;TreeNode result = inorderSuccessor(node4, node5);System.out.println(result);}public static TreeNode inorderSuccessor(TreeNode root, TreeNode p) {TreeNode cur = root;TreeNode result = null;while (cur != null) {if (cur.val > p.val) {result = cur;cur = cur.left;}else {cur = cur.right;}}return result;}
}

相关文章:

面试算法53:二叉搜索树的下一个节点

题目 给定一棵二叉搜索树和它的一个节点p&#xff0c;请找出按中序遍历的顺序该节点p的下一个节点。假设二叉搜索树中节点的值都是唯一的。例如&#xff0c;在图8.9的二叉搜索树中&#xff0c;节点8的下一个节点是节点9&#xff0c;节点11的下一个节点是null。 分析&#xf…...

2023SHCTF web方向wp

1.ezphp 看一眼&#xff0c;你大爷&#xff0c;啥玩意都给我过滤完了。 还好下面有preg_replace()/e&#xff0c;会把replacement当作php语句执行 传参pattern.*&#xff0c; .*表示任意字符&#xff0c;code{${phpinfo()}} &#xff0c;为什么这样写&#xff0c;因为,print_…...

从物理磁盘到数据库 —— 存储IO链路访问图

原图来自&#xff1a;数据库IO链路访问图 – OracleBlog 由于很复杂&#xff0c;为了加深理解自己重新画了一次&#xff0c;另外参考其他文档补充了各部分的插图和介绍。 一、 存储服务器 1. 物理磁盘 外层的壳子称为硬盘笼 cage 2. chunklet Chunklet 是一个虚拟概念而不是实…...

基于java+springboot+vue在线选课系统

项目介绍 本系统结合计算机系统的结构、概念、模型、原理、方法&#xff0c;在计算机各种优势的情况下&#xff0c;采用JAVA语言&#xff0c;结合SpringBoot框架与Vue框架以及MYSQL数据库设计并实现的。员工管理系统主要包括个人中心、课程管理、专业管理、院系信息管理、学生…...

GO学习之 同步操作sync包

GO系列 1、GO学习之Hello World 2、GO学习之入门语法 3、GO学习之切片操作 4、GO学习之 Map 操作 5、GO学习之 结构体 操作 6、GO学习之 通道(Channel) 7、GO学习之 多线程(goroutine) 8、GO学习之 函数(Function) 9、GO学习之 接口(Interface) 10、GO学习之 网络通信(Net/Htt…...

NUUO网络摄像头(NVR)RCE漏洞复现

简介 NUUO Network Video Recorder&#xff08;NVR&#xff09;是中国台湾NUUO公司的一款网络视频记录器。 NUUO NVR视频存储管理设备的__debugging_center_utils___.php文件存在未授权远程命令执行漏洞&#xff0c;攻击者可在没有任何权限的情况下通过log参数执行任意命令。…...

一款快速获取目标网站关键信息的工具

1.摘要 今天要介绍的这款工具是一个快速收集网站信息的开源脚本, 采用Python语言编写, 该工具可以快速收集网站的页面标题、网站上次更新日期、DNS信息、子域、防火墙名称、网站使用的技术栈、证书等信息, 默认支持对验证码和JavaScript内容执行绕过操作。 2.工具安装使用 使…...

将GC编程语言引入WebAssembly的新方法

本文讨论了一种名为 WasmGC 的新方法&#xff0c;用于将垃圾收集编程语言有效地引入 WebAssembly。 WasmGC 定义了新的 GC 类型&#xff0c;例如结构和数组&#xff0c;与之前编译为线性内存的方法 (WasmMVP) 相比&#xff0c;它们可以实现更好的优化&#xff1a; 在编译时和…...

微信小程序UI自动化测试实践:Minium+PageObject

小程序架构上分为渲染层和逻辑层&#xff0c;尽管各平台的运行环境十分相似&#xff0c;但是还是有些许的区别&#xff08;如下图&#xff09;&#xff0c;比如说JavaScript 语法和 API 支持不一致&#xff0c;WXSS 渲染表现也有不同&#xff0c;所以不论是手工测试&#xff0c…...

Java零基础入门-输入与输出

哈喽&#xff0c;各位小伙伴们&#xff0c;你们好呀&#xff0c;我是喵手。 今天我要给大家分享一些自己日常学习到的一些知识点&#xff0c;并以文字的形式跟大家一起交流&#xff0c;互相学习&#xff0c;一个人虽可以走的更快&#xff0c;但一群人可以走的更远。 我是一名后…...

iOS报错命名空间“std”中的“unary_function”

刚刚将我的 Xcode 升级到 15.0&#xff0c;突然它开始在 RCT_Folly 中出现以下错误 No template named unary_function in namespace std; did you mean __unary_function?我尝试删除缓存数据和派生数据并清理构建。也尝试删除 pod 和 node_modules。但没有任何帮助。 于是我…...

Flink SQL 窗口聚合详解

1.滚动窗⼝&#xff08;TUMBLE&#xff09; **滚动窗⼝定义&#xff1a;**滚动窗⼝将每个元素指定给指定窗⼝⼤⼩的窗⼝&#xff0c;滚动窗⼝具有固定⼤⼩&#xff0c;且不重叠。 例如&#xff0c;指定⼀个⼤⼩为 5 分钟的滚动窗⼝&#xff0c;Flink 将每隔 5 分钟开启⼀个新…...

中间件redis的使用

Java中的中间件配置体现在springboot的yml配置文件中。Springboot框架支持微服务和中间件和restful api远程服务的调用。中间件是Java web系统的中间层的服务系统的调用接口。Springboot的自动装配和约定大于配置机制初始化springcontext的容器空间和注册组件。使用容器管理服务…...

Why delete[] array when deepcopying with “=“?

代码负责释放对象之前已经分配的资源&#xff0c;比如堆上的内存。在执行深拷贝之前&#xff0c;你需要确保对象不再引用之前的资源&#xff0c;以避免内存泄漏。通过删除先前的资源&#xff0c;你可以确保在进行深拷贝之前&#xff0c;已经释放了之前的资源&#xff0c;从而避…...

curl(六)DNS解析、认证、代理

一 DNS解析 ① ip协议 使用ipv4 [-4] 还是ipv6 [-6] ② --resolve 场景&#xff1a; 在不修改系统配置文件 /etc/hosts 的情况下将单个请求临时固定到 ip 地址 1、使用 * 作为通配符,这样请求中调用的所有 Host 都 会转到你指定的 ip curl https://www.wzj.com --resolv…...

(免费领源码)PHP#MySQL高校学生信息管理系统28099-计算机毕业设计项目选题推荐

摘 要 随着互联网趋势的到来&#xff0c;各行各业都在考虑利用互联网将自己推广出去&#xff0c;最好方式就是建立自己的互联网系统&#xff0c;并对其进行维护和管理。在现实运用中&#xff0c;应用软件的工作规则和开发步骤&#xff0c;采用php技术建设学生信息管理系统设计。…...

[动态规划] (四) LeetCode 91.解码方法

[动态规划] (四) LeetCode 91.解码方法 91. 解码方法 题目解析 (1) 对字母A - Z进行编码1-26 (2)11106可以解码为1-1-10-6或者11-10-6, 但是11-1-06不能解码 (3) 0n不能解码 (4) 字符串非空&#xff0c;返回解码方法的总数 解题思路 状态表示 dp[i]&#xff1a;以i为结…...

Vue Vuex的使用和原理 专门解决共享数据的问题

Vuex专门解决共享数据的问题 多组件共享时使用&#xff0c;如用户ID各组件需要根据ID发送请求获取数据&#xff0c;任意组件可以进行增删改&#xff0c;相当于全局变量 Vuex 工作流程 如果确定值参数可以不经过Actions 直接走 安装Vuex vue2使用 vuex3 vue3使用 vuex4 npm i…...

第九周实验记录

1、安装Nerfstudio 环境配置 首先需要创建环境python3.8&#xff0c;接着需要安装cuda11.7或11.3 这里安装cuda11.7 pip uninstall torch torchvision functorchpip install torch1.13.1 torchvision functorch --extra-index-url https://download.pytorch.org/whl/cu117安…...

STM32WB55开发(6)----FUS更新

STM32WB55开发.6--FUS更新 概述视频教学硬件准备存储器映射FLASH安全区设置SRAM安全区设置通过USB进行下载注意事项 概述 在 STM32WB 微控制器中&#xff0c;FUS&#xff08;Firmware Upgrade Services&#xff09;是用于固件升级的一种服务。这项服务可以让你更新设备上的无…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...