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

寻找二叉树一个节点的后继节点

后继节点:中序遍历的后一个节点

普通二叉树:中序遍历得到一个list,时间复杂度O(n)

本题的二叉树:有父节点的指针,后继节点与原节点的距离为1,因此可以直接通过父节点找到下一个节点

优化:节点到另一个节点的真实距离为k,时间复杂度为O(k)

情况分析:

情况一:节点node有右子树,后继节点为右子树上的最左节点

情况二:节点node无右子树,沿着node向上找第一个作为左孩子的祖先,左孩子的父节点就是node的后继节点(因为此时节点node为节点Y左子树最右侧的节点

        对于情况二,在找到节点Y之后,节点Y即为node的后继节点,节点Y有没有右子树不重要

情况三:节点node本身为整颗二叉树最右的节点,没有后继节点,返回null

           

package binarytree;public class SuccessorNode {public class Node {int value;Node left;Node right;Node father;//这里定头节点的father节点为null,在创建二叉树时需要注意public Node(int data) {this.value = data;}}public Node getsuccessorNode(Node node) {if (node == null) {return node;}if (node.right != null) {//节点node有右子树while (node.left != null) {//找到最左的节点node = node.left;}return node;//返回右子树的最左节点} else {//没有右子树,向上找//node不为父节点的左孩子 并且 node的父节点不为null 则向上找while (node != node.father.left && node.father != null) {node = node.father;//此时为第一个不为右孩子的节点;此时为第一个为左孩子的节点}node = node.father;//如果node不是整颗二叉树的最右的节点,返回左孩子的父节点//如果node是整颗二叉树的最右的节点,node一直找到头节点,头节点的father为null,返回nullreturn node;}}}

 

相关文章:

寻找二叉树一个节点的后继节点

后继节点:中序遍历的后一个节点 普通二叉树:中序遍历得到一个list,时间复杂度O(n) 本题的二叉树:有父节点的指针,后继节点与原节点的距离为1,因此可以直接通过父节点找到下一个节点 优化:节点…...

如何能够获取到本行业的能力架构图去了解自己的能力缺陷与短板,从而能清晰的去弥补差距?

如何能够获取到本行业的能力架构图去了解自己的能力缺陷与短板,从而能清晰的去弥补差距? 获取并利用能力架构图(Competency Model)来了解自己在特定行业或职位中的能力缺陷和短板,并据此弥补差距,是一个非常…...

红队打靶:Misdirection打靶思路详解(vulnhub)

目录 写在开头 第一步:主机发现与端口扫描 第二步:Web渗透(80端口,战术放弃) 第三步:Web渗透(8080端口) 第四步:sudo bash提权 第五步:/etc/passwd利…...

10.23归并排序

课上 归并排序 最大时,就是两个都是完全倒序,但注意一定有一个序列先用完,此时剩一个序列只有一个元素,不用比较,直接加入,所以就是nn-1, 最小时,是都是完全有序,且一个序列中的元…...

[C++]:2初识C++(auto) + 类和对象上:

[TOC](初识C(auto) 类和对象上) 一.初始C 1.auto关键字:(C11) 1.作为一个变量的类型给这个类型初始化,auto自动识别初始化这个变量值的类型,为auto类型的这个变量开辟一个合适的空间。 补充: 1.typeid(变量名).name—>可以打…...

大学英语试卷

大学英语试卷 If everyone learns to set forth facts and reason things out in social life, many of the contradictions are easy to ____. A. oblige B. engage C. resolve D. commitIf we let the fastest runner set the____, the others will fall behind. A. pace B.…...

SpringBoot Lombok的使用

目录 下载Lombok插件 Lombok的用法 获取日志对象 生成get,set方法 Lombok框架的实现原理 Lombok的常用注解 下载Lombok插件 要使用Lombok首先要确保idea安装了lombok插件 在项目中添加 lombok依赖 在<dependency>里右键生成点击edit starters 插件(没有就下载,可…...

后台管理系统SQL注入漏洞

对于edu来说&#xff0c;是新人挖洞较好的平台&#xff0c;本次记录一次走运的捡漏0x01 前景 在进行fofa盲打站点的时候&#xff0c;来到了一个后台管理处看到集市二字&#xff0c;应该是edu站点 确认目标身份&#xff08;使用的quake进行然后去ipc备案查询&#xff09; 网…...

变量常用函数

查看变量类型 type(变量名) 用来查询变量所指的对象类型 >>> a, b, c, d 20, 5.5, True, 43j >>> print(type(a), type(b), type(c), type(d)) <class int> <class float> <class bool> <class complex> 基础数据类型 # coding…...

从零学算法(LCR 157)

某店铺将用于组成套餐的商品记作字符串 goods&#xff0c;其中 goods[i] 表示对应商品。请返回该套餐内所含商品的 全部排列方式 。 返回结果 无顺序要求&#xff0c;但不能含有重复的元素。 示例 1: 输入&#xff1a;goods “agew” 输出&#xff1a;[“aegw”,“aewg”,“ag…...

mysql 优化 聚簇索引=主键索引吗

在 InnoDB 引擎中&#xff0c;每张表都会有一个特殊的索引“聚簇索引”&#xff0c;也被称之为聚集索引&#xff0c;它是用来存储行数据的。一般情况下&#xff0c;聚簇索引等同于主键索引&#xff0c;但这里有一个前提条件&#xff0c;那就是这张表需要有主键&#xff0c;只有…...

c# ManualResetEvent WaitHandle 实现同步

//本文演示了ManualResetEvent 类的非静态set()、Reset()、WaitOne()和 //WaitHandle类的静态方法WaitAllWaitAll() //它们用于线程间的同步控制。 //实现了如下功能&#xff1a;线程1&#xff08;定时控制&#xff09;通知线程2和线程3采集数据 //线程2和3数据采集完了&am…...

使用Packstack安装器安装一体化OpenStack云平台

【实训目的】 初步掌握OpenStack快捷安装的方法。掌握OpenStack图形界面的基本操作。 【实训准备】 &#xff08;1&#xff09;准备一台能够安装OpenStack的实验用计算机&#xff0c;建议使用VMware虚拟机。 &#xff08;2&#xff09;该计算机应安装CentOS 7&#xff0c;建…...

【Rust】4 一文讲解重点 pattern matching | trait | 生命周期 | 闭包 | 迭代器 | 智能指针 | 并发与并行

文章目录 一、pattern matching二、trait2.1 常见 trait2.1.1 Copy 和 Clone2.1.2 PartialEq 和 Eq2.1.3 PartialOrd 和 Ord2.1.4 Hash2.1.5 From, Into, TryFrom, TryInto 2.2 概念2.2.1 关联类型2.2.2 关联常量2.3.3 泛型关联类型2.3.3.1 示例: 用泛型关联类型, 创建集合工厂…...

idea Java代码格式化规范

文章目录 引入基础知识代码模板idea模板eclipse模板1.安装插件2.生成配置文件3.导入配置文件 附录一&#xff1a;xml配置项说明附录二&#xff1a;赠送 引入 最近在公司开发中&#xff0c;遇到了一点小问题&#xff0c;组内各同事的格式化规范不一致。一来导致代码样式并不统一…...

apple MFI工厂认证,干货,为防止MFI工作人员查看,已设置VIP阅读

一开始以为审核特别严格,准备了好久,经历过了之后会发现很简单,1个小时完成了所有审核事项。 好好招待审计员,比如能接送就接送,到点吃饭就尽量约时间吃饭后再审计,找个正式的会议室,该摆盘水果就摆上,让审计员感觉到公司是很重视这次的MFI审核,但是不能贿赂发红包那…...

软件企业知识库应用场景?如何搭建软件企业知识库?

想要减少人工干预、减少不必要的时间和人力成本、快速获取准确信息……这些应用场景对于我们企业来说是非常渴望在短期内实现的。 软件企业知识库 因为传统知识库仅仅是存储&#xff1a;知识只是“存储”&#xff0c;根本用不起来&#xff0c;缺乏有效的管理方式和储存载体&am…...

华为OD 滑动窗口最大值(100分)【java】B卷

华为OD统一考试A卷+B卷 新题库说明 你收到的链接上面会标注A卷还是B卷。目前大部分收到的都是B卷。 B卷对应20022部分考题以及新出的题目,A卷对应的是新出的题目。 我将持续更新最新题目 获取更多免费题目可前往夸克网盘下载,请点击以下链接进入: 我用夸克网盘分享了「华为O…...

软件测试 (用例篇)

前言 上一篇博客讲述的是一次基本的测试过程。 在我们开始做了一段时间基础测试&#xff0c;熟悉了业务之后&#xff0c;往往会分配来写测试用例&#xff0c;并且在日常测试中&#xff0c;有时也需要补充测试用例到现有的案例库中。 在这里我们将回答以下问题 1、测试用例的…...

5G技术的飞速发展:连接未来

随着科技的日益进步&#xff0c;5G通讯技术已经成为了全球科技领域的热门话题。5G&#xff0c;即第五代移动通信技术&#xff0c;带来的不仅仅是更快的网络速度&#xff0c;它的高带宽和低延迟特性将为未来的数字世界奠定基础。 速度与效率的飞跃: 5G技术的最大亮点是它极高的下…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...