二叉树题目:输出二叉树
文章目录
- 题目
- 标题和出处
- 难度
- 题目描述
- 要求
- 示例
- 数据范围
- 前言
- 解法一
- 思路和算法
- 代码
- 复杂度分析
- 解法二
- 思路和算法
- 代码
- 复杂度分析
题目
标题和出处
标题:输出二叉树
出处:655. 输出二叉树
难度
6 级
题目描述
要求
给定二叉树的根结点 root \texttt{root} root,创建 m × n \texttt{m} \times \texttt{n} m×n 的字符串矩阵 res \texttt{res} res 表示二叉树的格式化输出。格式化输出矩阵应根据以下规则创建:
- 树的高度是 height \texttt{height} height,行数 m \texttt{m} m 应等于 height + 1 \texttt{height} + \texttt{1} height+1。
- 列数 n \texttt{n} n 应等于 2 height + 1 − 1 \texttt{2}^{\texttt{height} + \texttt{1}} - \texttt{1} 2height+1−1。
- 根结点放置在第一行的正中间(更正式而言,位于 res[0][(n - 1) / 2] \texttt{res[0][(n - 1) / 2]} res[0][(n - 1) / 2])。
- 对于每个放置在矩阵中 res[r][c] \texttt{res[r][c]} res[r][c] 位置的结点,将其左子结点放置在 res[r + 1][c − 2 height − r − 1 ] \texttt{res[r} + \texttt{1][c} - \texttt{2}^{\texttt{height} - \texttt{r} - \texttt{1}}\texttt{]} res[r+1][c−2height−r−1],右子结点放置在 res[r + 1][c + 2 height − r − 1 ] \texttt{res[r} + \texttt{1][c} + \texttt{2}^{\texttt{height} - \texttt{r} - \texttt{1}}\texttt{]} res[r+1][c+2height−r−1]。
- 重复该过程,直到所有结点都放置到矩阵中。
- 所有空单元格应包含空字符串 "" \texttt{""} ""。
返回创建的矩阵 res \texttt{res} res。
示例
示例 1:
输入: root = [1,2] \texttt{root = [1,2]} root = [1,2]
输出:
[["", "1", ""], \texttt{[["", "1", ""],} [["", "1", ""],
["2", "", ""]] \texttt{ ["2", "", ""]]} ["2", "", ""]]
示例 2:
输入: root = [1,2,3,null,4] \texttt{root = [1,2,3,null,4]} root = [1,2,3,null,4]
输出:
[["", "", "", "1", "", "", ""], \texttt{[["", "", "", "1", "", "", ""],} [["", "", "", "1", "", "", ""],
["", "2", "", "", "", "3", ""], \texttt{ ["", "2", "", "", "", "3", ""],} ["", "2", "", "", "", "3", ""],
["", "", "4", "", "", "", ""]] \texttt{ ["", "", "4", "", "", "", ""]]} ["", "", "4", "", "", "", ""]]
数据范围
- 树中结点数目在范围 [1, 2 10 ] \texttt{[1, 2}^\texttt{10}\texttt{]} [1, 210] 内
- -99 ≤ Node.val ≤ 99 \texttt{-99} \le \texttt{Node.val} \le \texttt{99} -99≤Node.val≤99
- 树的高度在范围 [1, 10] \texttt{[1, 10]} [1, 10] 内
前言
这道题要求将给定的二叉树格式化输出,使用矩阵表示格式化输出的结果。由于矩阵的行数和列数由二叉树的高度决定,因此需要首先计算二叉树的高度,根据二叉树的高度计算矩阵的行数和列数,创建矩阵之后遍历二叉树并将每个结点值填入矩阵中的对应位置。
计算二叉树的高度可以使用「二叉树的最大深度」的做法,使用深度优先搜索或者广度优先搜索得到二叉树的高度。这道题中定义的二叉树的高度为从根结点到最远叶结点的路径上的边数,因此边界情况为只有一个结点的二叉树的高度是 0 0 0。
得到二叉树的高度 height \textit{height} height 之后,即可得到矩阵的行数 m = height + 1 m = \textit{height} + 1 m=height+1,列数 n = 2 m − 1 n = 2^m - 1 n=2m−1。创建矩阵之后,首先将根结点值填入矩阵的第 0 0 0 行第 n − 1 2 \dfrac{n - 1}{2} 2n−1 列,然后遍历二叉树的其余结点并填入矩阵中的对应位置。
当一个结点的位置确定之后,可以根据该结点在矩阵中的行列下标以及二叉树的高度决定其子结点的位置。如果一个结点位于第 row \textit{row} row 行第 column \textit{column} column 列,则其左子结点位于第 row + 1 \textit{row} + 1 row+1 行第 column − 2 height − row − 1 \textit{column} - 2^{\textit{height} - \textit{row} - 1} column−2height−row−1 列,其右子结点位于第 row + 1 \textit{row} + 1 row+1 行第 column + 2 height − row − 1 \textit{column} + 2^{\textit{height} - \textit{row} - 1} column+2height−row−1 列。
输出二叉树可以使用深度优先搜索或者广度优先搜索实现。
解法一
思路和算法
使用深度优先搜索输出二叉树时,首先将根结点值填入矩阵的第 0 0 0 行第 n − 1 2 \dfrac{n - 1}{2} 2n−1 列,然后计算出非空子结点在矩阵中的位置,继续遍历非空子树并将其余的结点值填入矩阵,直到所有结点遍历完毕,此时所有结点值都填入矩阵中的对应位置。
整个过程是一个递归的过程,递归的终止条件是当前结点为叶结点,此时将当前结点值填入矩阵中的对应位置,然后直接返回。对于其余情况,在将当前结点值填入矩阵中的对应位置之后,对非空子结点执行递归。
代码
class Solution {List<List<String>> res = new ArrayList<List<String>>();int height;public List<List<String>> printTree(TreeNode root) {height = getHeight(root);int m = height + 1;int n = (1 << m) - 1;for (int i = 0; i < m; i++) {List<String> row = new ArrayList<String>();for (int j = 0; j < n; j++) {row.add("");}res.add(row);}dfs(root, 0, (n - 1) / 2);return res;}public int getHeight(TreeNode root) {TreeNode left = root.left, right = root.right;if (left == null && right == null) {return 0;}int leftHeight = left != null ? getHeight(left) : -1;int rightHeight = right != null ? getHeight(right) : -1;return Math.max(leftHeight, rightHeight) + 1;}public void dfs(TreeNode node, int row, int column) {res.get(row).set(column, String.valueOf(node.val));TreeNode left = node.left, right = node.right;if (left != null) {dfs(left, row + 1, column - (1 << (height - row - 1)));}if (right != null) {dfs(right, row + 1, column + (1 << (height - row - 1)));}}
}
复杂度分析
-
时间复杂度: O ( h × 2 h ) O(h \times 2^h) O(h×2h),其中 h h h 是二叉树的高度。矩阵的行数 m m m 和列数 n n n 满足 m = h + 1 m = h + 1 m=h+1, n = 2 h + 1 − 1 n = 2^{h + 1} - 1 n=2h+1−1,输出二叉树的时间复杂度是 O ( m n ) = O ( h × 2 h ) O(mn) = O(h \times 2^h) O(mn)=O(h×2h)。
-
空间复杂度: O ( h ) O(h) O(h),其中 h h h 是二叉树的高度。空间复杂度主要是递归调用的栈空间,取决于二叉树的高度。注意返回值不计入空间复杂度。
解法二
思路和算法
使用广度优先搜索输出二叉树时,使用两个队列分别存储待访问的结点和结点在矩阵中的位置,两个队列分别为结点队列和位置队列。初始时,将根结点入结点队列,将第 0 0 0 行第 n − 1 2 \dfrac{n - 1}{2} 2n−1 列入位置队列。
每次将一个结点从结点队列出队,并将一个位置从位置队列出队,出队的位置即为出队的结点在矩阵中的位置。将当前结点值填入矩阵中的对应位置,然后计算出非空子结点在矩阵中的位置,将非空子结点和对应位置分别入两个队列。重复该过程直到所有结点遍历完毕,此时所有结点值都填入矩阵中的对应位置。
代码
class Solution {public List<List<String>> printTree(TreeNode root) {int height = getHeight(root);int m = height + 1;int n = (1 << m) - 1;List<List<String>> res = new ArrayList<List<String>>();for (int i = 0; i < m; i++) {List<String> row = new ArrayList<String>();for (int j = 0; j < n; j++) {row.add("");}res.add(row);}Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();Queue<int[]> locationQueue = new ArrayDeque<int[]>();nodeQueue.offer(root);locationQueue.offer(new int[]{0, (n - 1) / 2});while (!nodeQueue.isEmpty()) {TreeNode node = nodeQueue.poll();int[] location = locationQueue.poll();int row = location[0], column = location[1];res.get(row).set(column, String.valueOf(node.val));TreeNode left = node.left, right = node.right;if (left != null) {nodeQueue.offer(left);locationQueue.offer(new int[]{row + 1, column - (1 << (height - row - 1))});}if (right != null) {nodeQueue.offer(right);locationQueue.offer(new int[]{row + 1, column + (1 << (height - row - 1))});}}return res;}public int getHeight(TreeNode root) {int depth = -1;Queue<TreeNode> queue = new ArrayDeque<TreeNode>();queue.offer(root);while (!queue.isEmpty()) {depth++;int size = queue.size();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}return depth;}
}
复杂度分析
-
时间复杂度: O ( h × 2 h ) O(h \times 2^h) O(h×2h),其中 h h h 是二叉树的高度。矩阵的行数 m m m 和列数 n n n 满足 m = h + 1 m = h + 1 m=h+1, n = 2 h + 1 − 1 n = 2^{h + 1} - 1 n=2h+1−1,输出二叉树的时间复杂度是 O ( m n ) = O ( h × 2 h ) O(mn) = O(h \times 2^h) O(mn)=O(h×2h)。
-
空间复杂度: O ( 2 h ) O(2^h) O(2h),其中 h h h 是二叉树的高度。空间复杂度主要是队列空间,队列内元素个数不超过二叉树的结点数,高度为 h h h 的二叉树中最多有 2 h + 1 − 1 2^{h + 1} - 1 2h+1−1 个结点。注意返回值不计入空间复杂度。
相关文章:

二叉树题目:输出二叉树
文章目录 题目标题和出处难度题目描述要求示例数据范围 前言解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目 标题和出处 标题:输出二叉树 出处:655. 输出二叉树 难度 6 级 题目描述 要求 给定二叉树的根结点 root \textt…...
apache poi_5.2.5 实现对表格单元格的自定义变量名进行图片替换
apache poi_5.2.5 实现对表格单元格的自定义变量名进行图片替换 实现思路 1.首先定位到自定义变量名 2.然后先清除自定义变量名,可利用setText(null,0)来清除 3.在自定义变量名的位置添加图片,使用下面的代码 4.对于图片布局有要求的,利用C…...

Kafka--Kafka日志索引详解以及生产常见问题分析与总结
一、Kafka的Log日志梳理 这一部分数据主要包含当前Broker节点的消息数据(在Kafka中称为Log日志)。这是一部分无状态的数据,也就是说每个Kafka的Broker节点都是以相同的逻辑运行。这种无状态的服务设计让Kafka集群能够比较容易的进行水平扩展。比如你需要用一个新…...

Vue3-23-组件-依赖注入的使用详解
什么是依赖注入 个人的理解 : 依赖注入,是在 一颗 组件树中,由 【前代组件】 给 【后代组件】 提供 属性值的 一种方式 ;这种方式 突破了 【父子组件】之间通过 props 的方式传值的限制,只要是 【前代组件】提供的 依…...

css 美化滚动条
当div内容溢出容器定义的高度时,滚动条显示,并美化默认的滚动条样式 div 容器 <divclass"content">内容 </div>css 样式 /* 问话区域 滚动条 */ .content {overflow: auto;height: 662px;padding: 25px;scrollbar-width: thin; /* 设置滚动条宽度 */bo…...
Tomcat介绍及使用:构建强大的Java Web应用服务器
引言: 在现代软件开发中,Web应用已经成为了不可或缺的一部分。而为了构建高效、稳定的Web应用服务器,选择合适的工具和技术至关重要。Tomcat作为一款开源的Java Web应用服务器,凭借其丰富的功能和灵活的配置,成为了开发…...

怎么定义一套完成标准的JAVA枚举类型
一、背景 在java代码中,接口返回有各种各样的状态,比如400 401 200 500 403等常见的http状态码,也有我们自定义的很多业务状态码。如果系统比较复杂,制定一套完整的标准的状态码是非常有必要的,这样比较方面BUG排查。…...

Apache Seatunnel本地源码构建编译运行调试
Apache Seatunnel本地源码构建编译运行调试 文章目录 1. 环境准备1.1 Java环境1.2 Maven1.3 IDEA1.4 Docker环境1.5 Mysql8.0.281.6 其它环境准备 2. 源码包下载3. idea项目配置3.1 项目导入3.2 maven配置3.3 项目JDK配置3.4 项目启动参数配置3.4.1 seatunnel项目启动参数配置3…...

构建高效持久层:深度解析 MyBatis-Plus(02)
目录 引言1. 逻辑删除1.1 概述1.2 逻辑删除的优势1.3.为什么使用逻辑删除1.4 综合案例 2. 乐观锁和悲观锁2.1.什么是乐观锁和悲观锁2.2.乐观锁和悲观锁的区别2.3.综合案例 3. 分页插件总结 引言 在现代软件开发中,数据库操作是不可或缺的一环。为了提高系统的性能、…...

Gitlab仓库推送到Gitee仓库的一种思路
文章目录 Gitlab仓库推送到Gitee仓库的一种思路1、创建Gitee的ssh公钥(默认已有Gitlab的ssh公钥)2、添加Gitlab远程仓库地址3、添加Gitee远程仓库地址4、拉取Gitlab远程仓库指定分支到本地仓库指定分支(以test分支为例)5、推送本地…...

快速能访问服务器的文件
1、背景 访问ubuntu上的文件 2、方法 python3 -m http.server 8081 --directory /home/ NAS 共享访问协议 — NFS、SMB、FTP、WebDAV 各有何优势?http://1 Ubuntu 搭建文件服务器(Nginx)...

Diary26-Vue综合案例1-书籍购物车
Vue综合案例1-书籍购物车 案例要求: 代码: <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewpor…...

【EasyExcel实践】万能导出,一个接口导出多张表以及任意字段(可指定字段顺序)-简化升级版
文章目录 前言正文一、项目简介二、核心代码2.1 pom.xml 依赖配置2.2 ExcelHeadMapFactory2.3 ExcelDataLinkedHashMap2.4 自定义注解 ExcelExportBean2.5 自定义注解 ExcelColumnTitle2.6 建造器接口 Builder2.7 表格工具类 ExcelUtils2.8 GsonUtil2.9 模版类 ExportDynamicCo…...

解决 Hive 外部表分隔符问题的实用指南
简介: 在使用 Hive 外部表时,分隔符设置不当可能导致数据导入和查询过程中的问题。本文将详细介绍如何解决在 Hive 外部表中正确设置分隔符的步骤。 问题描述: 在使用Hive外部表时,可能会遇到分隔符问题。这主要是因为Hive在读…...
一文学会 Apache Zeppelin
Zeppelin资料 Zeppelin项目信息 Zeppelin官网 http://zeppelin.apache.org/Zeppelin源码地址 https://github.com/apache/zeppelinZeppelin JIRA: https://issues.apache.org/jira/projects/ZEPPELIN/summaryZeppelin文档 Flink on Zeppelin 文档集中地 https://www.yuque.co…...

ROS学习笔记(七)---参数服务器
ROS学习笔记文章目录 01. ROS学习笔记(一)—Linux安装VScode 02. ROS学习笔记(二)—使用 VScode 开发 ROS 的Python程序(简例) 03. ROS学习笔记(三)—好用的终端Terminator 04. ROS学习笔记(四)—使用 VScode 启动launch文件运行多个节点 05. ROS学习笔…...

【RTOS学习】源码分析(信号量和互斥量 事件组 任务通知)
🐱作者:一只大喵咪1201 🐱专栏:《RTOS学习》 🔥格言:你只管努力,剩下的交给时间! 目录 🍓信号量和互斥量🍅创建🍅Take🍅Give &#x…...
1316:【例4.6】数的计数(Noip2001) 代码+解析
1316:【例4.6】数的计数(Noip2001) 【题目描述】 我们要求找出具有下列性质数的个数(包括输入的自然数n )。先输入一个自然数n(n≤1000),然后对此自然数按照如下方法进行处理:不作任何处理;在它的左边加上一…...

征集倒计时 | 2023年卓越影响力榜单-第四届中国产业创新奖报名即将截止
第四届「ISIG中国产业智能大会」将于2024年3月16日在上海举办。2024 ISIG 以“与科技共赢,与产业共进”为主题,共设立RPA超自动化、 低代码、AIGC大模型、流程挖掘四大主题峰会。届时,大会组委会将颁发2023年度卓越影响力榜单—第四届中国产业…...

vue的语法模板与数据绑定的说明
vue的两大模板语法: 1.插值语法 2.指定语法 插值语法:{{}} 功能:用于解析标签体的内容 写法:{{xxx}},xxx是js表达式,且可以直接读取到data中的所有属性 指定语法: 功能:用于解析标签(包括:标签属性、标…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...

家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...

LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式
简介 在我的 QT/C 开发工作中,合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式:工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...

云原生安全实战:API网关Envoy的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关 作为微服务架构的统一入口,负责路由转发、安全控制、流量管理等核心功能。 2. Envoy 由Lyft开源的高性能云原生…...

大模型——基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程
基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程 下载安装Docker Docker官网:https://www.docker.com/ 自定义Docker安装路径 Docker默认安装在C盘,大小大概2.9G,做这行最忌讳的就是安装软件全装C盘,所以我调整了下安装路径。 新建安装目录:E:\MyS…...