每日算法之二叉树的下一个结点
2023-03-31 10:43:29 时间
JZ8二叉树的下一个结点
描述
给定一个二叉树其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的next指针。
示例:
输入:{8,6,10,5,7,9,11},8
返回:9
解析:这个组装传入的子树根节点,其实就是整颗树,中序遍历{5,6,7,8,9,10,11},根节点8的下一个节点就是9,应该返回{9,10,11},后台只打印子树的下一个节点,所以只会打印9
具体做法:
step 1:首先先根据当前给出的结点找到根节点
step 2:然后根节点调用中序遍历
step 3:将中序遍历结果存储下来
step 4:最终拿当前结点匹配是否有符合要求的下一个结点
代码
package mid.JZ8二叉树的下一个结点;
import java.util.ArrayList;
class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
public class Solution {
ArrayList<TreeLinkNode> nodes = new ArrayList<>();
public TreeLinkNode GetNext(TreeLinkNode pNode) {
TreeLinkNode root = pNode;
//获取根节点
while (root.next != null) root = root.next;
//获取中序遍历集合
inOrder(root);
//匹配
for (int i = 0; i < nodes.size() - 1; i++) {
if (pNode.val == nodes.get(i).val) {
return nodes.get(i + 1);
}
}
return null;
}
public void inOrder(TreeLinkNode root) {
if (root != null) {
inOrder(root.left);
nodes.add(root);
inOrder(root.right);
}
}
}
相关文章
- 关于静态代码块和匿名代码块以及结构体在程序运行过程中的调用顺序实验(续)
- CSS响应式布局(自适应布局)
- 关于静态代码块和匿名代码块以及结构体在程序运行过程中的调用顺序实验
- 案例分析|如何消除代码坏味道
- SpringBoot配置与打包基础
- 《分布式技术原理与算法解析》学习笔记Day14
- pinia和vuex的区别 Vuex 和 Pinia 的优缺点 何时使用Pinia,何时使用Vuex
- 微信小程序登录方法,授权登陆及获取微信用户手机号
- Spring的第一个程序和IOC创建对象方式
- 前端如何将项目部署到服务器(Nginx)
- 《分布式技术原理与算法解析》学习笔记Day13
- 快速搭建一个网关服务,动态路由、鉴权,一网打尽!(含流程图)
- 记住这些windows网络操作命令,轻松搞定自己的电脑网络!
- 《分布式技术原理与算法解析》学习笔记Day12
- C++——WebServer服务器项目
- 基于Java Web的随意购商城系统(开源项目)
- RabbitMQ-消息中间键
- 【node】升级 Node 版本教程
- Linux环境中下载安装Maven
- OpenFeign-远程调用工具