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

后继节点:中序遍历的后一个节点
普通二叉树:中序遍历得到一个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来说,是新人挖洞较好的平台,本次记录一次走运的捡漏0x01 前景 在进行fofa盲打站点的时候,来到了一个后台管理处看到集市二字,应该是edu站点 确认目标身份(使用的quake进行然后去ipc备案查询) 网…...
变量常用函数
查看变量类型 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,其中 goods[i] 表示对应商品。请返回该套餐内所含商品的 全部排列方式 。 返回结果 无顺序要求,但不能含有重复的元素。 示例 1: 输入:goods “agew” 输出:[“aegw”,“aewg”,“ag…...
mysql 优化 聚簇索引=主键索引吗
在 InnoDB 引擎中,每张表都会有一个特殊的索引“聚簇索引”,也被称之为聚集索引,它是用来存储行数据的。一般情况下,聚簇索引等同于主键索引,但这里有一个前提条件,那就是这张表需要有主键,只有…...
c# ManualResetEvent WaitHandle 实现同步
//本文演示了ManualResetEvent 类的非静态set()、Reset()、WaitOne()和 //WaitHandle类的静态方法WaitAllWaitAll() //它们用于线程间的同步控制。 //实现了如下功能:线程1(定时控制)通知线程2和线程3采集数据 //线程2和3数据采集完了&am…...
使用Packstack安装器安装一体化OpenStack云平台
【实训目的】 初步掌握OpenStack快捷安装的方法。掌握OpenStack图形界面的基本操作。 【实训准备】 (1)准备一台能够安装OpenStack的实验用计算机,建议使用VMware虚拟机。 (2)该计算机应安装CentOS 7,建…...
【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.导入配置文件 附录一:xml配置项说明附录二:赠送 引入 最近在公司开发中,遇到了一点小问题,组内各同事的格式化规范不一致。一来导致代码样式并不统一…...
apple MFI工厂认证,干货,为防止MFI工作人员查看,已设置VIP阅读
一开始以为审核特别严格,准备了好久,经历过了之后会发现很简单,1个小时完成了所有审核事项。 好好招待审计员,比如能接送就接送,到点吃饭就尽量约时间吃饭后再审计,找个正式的会议室,该摆盘水果就摆上,让审计员感觉到公司是很重视这次的MFI审核,但是不能贿赂发红包那…...
软件企业知识库应用场景?如何搭建软件企业知识库?
想要减少人工干预、减少不必要的时间和人力成本、快速获取准确信息……这些应用场景对于我们企业来说是非常渴望在短期内实现的。 软件企业知识库 因为传统知识库仅仅是存储:知识只是“存储”,根本用不起来,缺乏有效的管理方式和储存载体&am…...
华为OD 滑动窗口最大值(100分)【java】B卷
华为OD统一考试A卷+B卷 新题库说明 你收到的链接上面会标注A卷还是B卷。目前大部分收到的都是B卷。 B卷对应20022部分考题以及新出的题目,A卷对应的是新出的题目。 我将持续更新最新题目 获取更多免费题目可前往夸克网盘下载,请点击以下链接进入: 我用夸克网盘分享了「华为O…...
软件测试 (用例篇)
前言 上一篇博客讲述的是一次基本的测试过程。 在我们开始做了一段时间基础测试,熟悉了业务之后,往往会分配来写测试用例,并且在日常测试中,有时也需要补充测试用例到现有的案例库中。 在这里我们将回答以下问题 1、测试用例的…...
5G技术的飞速发展:连接未来
随着科技的日益进步,5G通讯技术已经成为了全球科技领域的热门话题。5G,即第五代移动通信技术,带来的不仅仅是更快的网络速度,它的高带宽和低延迟特性将为未来的数字世界奠定基础。 速度与效率的飞跃: 5G技术的最大亮点是它极高的下…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
