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

【二叉树】Leetcode 114. 二叉树展开为链表【中等】

二叉树展开为链表

给你二叉树的根结点 root ,请你将它展开为一个单链表:

  • 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例1:
在这里插入图片描述
输入:root = [1,2,5,3,4,null,6]
输出:[1,null,2,null,3,null,4,null,5,null,6]

解题思路

展开二叉树为单链表可以使用前序遍历的方式来实现。

  • 1、对于当前节点,首先将其左子树展开为单链表,并将左子树的最右节点连接到当前节点的右子树上。
  • 2、然后将当前节点的右子树展开为单链表。
  • 3、如果左子树不为空,将当前节点的右子树设为展开后的左子树;否则,将左子树设为右子树。

Java实现

public class FlattenBinaryTreeToLinkedList {static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}}public void flatten(TreeNode root) {if (root == null) {return;}flattenHelper(root);}private TreeNode flattenHelper(TreeNode node) {if (node == null) {return null;}//    1//   / \//  2   5// / \   \//3   4   6// 把2的右子树4放到2的左子树3的右子树上//      1//     / \//    2   5//   / \   \//  3   4   6//   \//    4//把2左子树3-4移到右子树下,把2的左子树置空//      1//     / \//    2   5//     \   \//      3   6//       \//        4//递归,把1的右子树5-6移到1的左子树2-3-4的右子树下//      1//     / \//    2   5//     \   \//      3   6//       \//        4//         \//          5//           \//            6//把1的左子树2-3-4-5-6替换到右子树上,把1的左子树置空//      1//       \//        2//         \//          3//           \//            4//             \//              5//               \//                6//链表符合前序遍历了,并且左子树全为null//下面是具体代码实现TreeNode leftTail = flattenHelper(node.left);TreeNode rightTail = flattenHelper(node.right);if (leftTail != null) {// 把右子树放到左子树的右子树上leftTail.right = node.right;// 把(带有右子树的)左子树赋给右子树node.right = node.left;// 右子树清空node.left = null;}//        在这里,rightTail 的优先级最高,然后是 leftTail,最后是 node。
//        这确保了在递归的过程中,当前子树展开后的链表的尾节点是按照
//        右子树、左子树、当前节点的顺序确定的。
//        这样的顺序保证了链表的正确连接,即右子树的尾部接在左子树的尾部,
//        而左子树的尾部接在当前节点的右侧。这样展开后的链表顺序符合二叉树的先序遍历。return (rightTail != null) ? rightTail : (leftTail != null) ? leftTail : node;}// 示例测试public static void main(String[] args) {FlattenBinaryTreeToLinkedList solution = new FlattenBinaryTreeToLinkedList();// 构造示例二叉树TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(5);root.left.left = new TreeNode(3);root.left.right = new TreeNode(4);root.right.right = new TreeNode(6);// 调用展开方法solution.flatten(root);// 打印展开后的链表TreeNode current = root;while (current != null) {System.out.print(current.val + " ");current = current.right;}}
}

时间空间复杂度

  • 时间复杂度:O(n),其中n是二叉树中的节点数,每个节点都需要访问一次。
  • 空间复杂度:O(h),递归调用栈的深度为树的高度。

相关文章:

【二叉树】Leetcode 114. 二叉树展开为链表【中等】

二叉树展开为链表 给你二叉树的根结点 root ,请你将它展开为一个单链表: 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同…...

2024年150道高频Java面试题(二十)

39. 说一下 HashMap 的实现原理? HashMap 是 Java 中使用非常普遍的一种基于散列的映射数据结构,主要用于存储键值对。它允许使用任何非空对象作为键和值,主要实现原理如下: 数组 链表 红黑树:HashMap 内部主要由一…...

Docker-Compose容器编排

​ 基本介绍 使用一个Dockerfile模板文件,可以很方便的定义一个适合自己使用的自定义镜像。但在工作中经常会碰到需要多个容器相互配合来完成某项任务或运行某个项目的情况。例如要运行一个django项目,除了django容器本身,往往还需要再加上…...

nvm 安装多个版本的Node npm

先安装nvm 管理工具 git安装地址 找到安装包 下载然后安装 https://github.com/coreybutler/nvm-windows/releases/tag/1.1.11nvm常用命令 命令说明nvm version查看nvm版本nvm ls查看所有已经安装的Nodejs版本nvm list installed查看所有已经安装的Nodejs版本nvm ls availab…...

RisingWave 在品高股份 Bingo IAM 中的应用

背景介绍 公司背景 品高股份,是国内专业的云计算及行业信息化服务提供商。公司成立于 2003 年,总部位于广州,下设多家子公司和分公司,目前员工总数近 900 人,其中 80 %以上是专业技术人员。 品高股份在 2008 年便开…...

.Net Core/.Net6/.Net8 ,启动配置/Program.cs 配置

.Net Core/.Net6/.Net8 &#xff0c;启动配置/Program.cs 配置 没有废话&#xff0c;直接上代码调用 没有废话&#xff0c;直接上代码 /// <summary>/// 启动类/// </summary>public static class Mains{static IServiceCollection _services;static IMvcBuilder _…...

尚硅谷2024最新Git企业实战教程 | Git与GitLab的企业实战

这篇博客是尚硅谷2024最新Git企业实战教程&#xff0c;全方位学习git与gitlab的完整笔记。 这不仅仅是一套Git的入门教程&#xff0c;更是全方位的极狐GitLab企业任务流开发实战&#xff01;作为一应俱全的一站式DevOps平台&#xff0c;极狐GitLab的高阶功能全面覆盖&#xff0…...

2024阿里云老用户服务器优惠价格99元和199元

阿里云服务器租用价格表2024年最新&#xff0c;云服务器ECS经济型e实例2核2G、3M固定带宽99元一年&#xff0c;轻量应用服务器2核2G3M带宽轻量服务器一年61元&#xff0c;ECS u1服务器2核4G5M固定带宽199元一年&#xff0c;2核4G4M带宽轻量服务器一年165元12个月&#xff0c;2核…...

【前端webpack5高级优化】提升打包构建速度几种优化方案

HotModuleReplacement&#xff08;HMR/热模块替换&#xff09; 开发时我们修改了其中一个模块代码&#xff0c;Webpack 默认会将所有模块全部重新打包编译&#xff0c;速度很慢 所以我们需要做到修改某个模块代码&#xff0c;就只有这个模块代码需要重新打包编译&#xff0c;…...

【第十一届大唐杯全国大学生新一代信息通信技术大赛】赛题分析

赛道一 一等奖 7% 二等奖 15% 三等奖 25% 赛道二 参考文档&#xff1a; 《第十一届大唐杯全国大学生新一代信息通信技术大赛&#xff08;产教融合5G创新应用设计&#xff09;专项赛说明.pdf》 一等奖&#xff1a;7% 二等奖&#xff1a;10% 三等奖&#xff1a;20% 赛项一&am…...

Java面试题:Java集合框架:请简述Java集合框架的主要组成部分,并解释它们之间的关系。

Java集合框架&#xff08;Java Collections Framework&#xff09;是一组用来表示和操作集合的类的集合&#xff0c;它提供了用于存储不同类型对象的标准化接口和类。Java集合框架的主要组成部分包括以下几个部分&#xff1a; 集合接口&#xff08;Collection Interface&#…...

hadoop3.0高可用分布式集群安装

hadoop高可用&#xff0c;依赖于zookeeper。 用于生产环境, 企业部署必须的模式. 1. 部署环境规划 1.1. 虚拟机及hadoop角色划分 主机名称 namenode datanode resourcemanager nodemanager zkfc journalnode zookeeper master slave1 slave2 1.2. 软件版本 java …...

Flink SQL系列之:解析Debezium数据格式时间字段常用的函数

Flink SQL系列之:解析Debezium数据格式时间字段常用的函数 一、FROM_UNIXTIME二、DATE_FORMAT三、TO_DATE四、CAST五、TO_TIMESTAMP_LTZ六、CONVERT_TZ七、FROM_UNIXTIME八、TO_TIMESTAMP九、常见用法案例1.案例一2.案例二3.案例三4.案例四5.案例五...

Redis底层数据结构-Dict

1. Dict基本结构 Redis的键与值的映射关系是通过Dict来实现的。 Dict是由三部分组成&#xff0c;分别是哈希表&#xff08;DictHashTable&#xff09;&#xff0c;哈希节点&#xff08;DictEntry&#xff09;&#xff0c;字典&#xff08;Dict&#xff09; 哈希表结构如下图所…...

Python基于深度学习的人脸识别项目源码+演示视频,利用OpenCV进行人脸检测与识别 preview

​ 一、原理介绍 该人脸识别实例是一个基于深度学习和计算机视觉技术的应用&#xff0c;主要利用OpenCV和Python作为开发工具。系统采用了一系列算法和技术&#xff0c;其中包括以下几个关键步骤&#xff1a; 图像预处理&#xff1a;首先&#xff0c;对输入图像进行预处理&am…...

CTF下加载CTFtraining题库以管理员身份导入 [HCTF 2018]WarmUp,之后以参赛者身份完成解题全过程

-------------------搭建CTFd------------------------------ 给大家介绍一个本地搭建比较好用的CTF比赛平台&#xff1a;CTFD。 CTFd是一个Capture The Flag框架&#xff0c;侧重于易用性和可定制性。它提供了运行CTF所需的一切&#xff0c;并且可以使用插件和主题轻松进行自…...

机器学习每周挑战——信用卡申请用户数据分析

数据集的截图 # 字段 说明 # Ind_ID 客户ID # Gender 性别信息 # Car_owner 是否有车 # Propert_owner 是否有房产 # Children 子女数量 # Annual_income 年收入 # Type_Income 收入类型 # Education 教育程度 # Marital_status 婚姻状况 # Housing_type 居住…...

Vulnhub:WESTWILD: 1.1

目录 信息收集 arp nmap nikto whatweb WEB web信息收集 dirmap enm4ulinux sumbclient get flag1 ssh登录 提权 横向移动 get root 信息收集 arp ┌──(root㉿ru)-[~/kali/vulnhub] └─# arp-scan -l Interface: eth0, type: EN10MB, MAC: 0…...

[C#]winform使用OpenCvSharp实现透视变换功能支持自定义选位置和删除位置

【透视变换基本原理】 OpenCvSharp 是一个.NET环境下对OpenCV原生库的封装&#xff0c;它提供了大量的计算机视觉和图像处理的功能。要使用OpenCvSharp实现透视变换&#xff08;Perspective Transformation&#xff09;&#xff0c;你首先需要理解透视变换的原理和它在图像处理…...

C++——list类及其模拟实现

前言&#xff1a;这篇文章我们继续进行C容器类的分享——list&#xff0c;也就是数据结构中的链表&#xff0c;而且是带头双向循环链表。 一.基本框架 namespace Mylist {template<class T>//定义节点struct ListNode{ListNode<T>* _next;ListNode<T>* _pre…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...

五子棋测试用例

一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏&#xff0c;有着深厚的文化底蕴。通过将五子棋制作成网页游戏&#xff0c;可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家&#xff0c;都可以通过网页五子棋感受到东方棋类…...

自然语言处理——文本分类

文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益&#xff08;IG&#xff09; 分类器设计贝叶斯理论&#xff1a;线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别&#xff0c; 有单标签多类别文本分类和多…...