企业站,南京软件定制开发,衡阳网站建设网站,网站建设责任分工表#x1f600;前言 在算法面试中#xff0c;二叉树的层序遍历是一个经典的题目。而这道题的要求是进一步将二叉树的每一层结点值打印成多行#xff0c;即同一层结点从左至右输出#xff0c;最终结果存放到一个二维数组中返回。接下来#xff0c;我们将通过代码实例详细解析… 前言 在算法面试中二叉树的层序遍历是一个经典的题目。而这道题的要求是进一步将二叉树的每一层结点值打印成多行即同一层结点从左至右输出最终结果存放到一个二维数组中返回。接下来我们将通过代码实例详细解析解题思路。 个人主页尘觉主页 文章目录 把二叉树打印成多行题目描述数据范围要求 示例示例1示例2示例3示例4 解题思路代码实现详细解析 总结 把二叉树打印成多行
NowCoder
题目描述
给定一个节点数为 n 的二叉树要求从上到下按层打印二叉树的 val 值同一层节点从左至右输出每一层输出一行将输出的结果存放到一个二维数组中返回。
以二叉树 {1,2,3,#,#,4,5} 为例它的层序遍历结果如下
[[1],[2,3],[4,5]
]数据范围
二叉树的节点数 0 ≤ n ≤ 1000每个节点的值 0 ≤ val ≤ 1000
要求
时间复杂度O(n)空间复杂度O(n)
示例
示例1
输入{1,2,3,#,#,4,5}
返回值[[1],[2,3],[4,5]]
示例2
输入{8,6,10,5,7,9,11}
返回值[[8],[6,10],[5,7,9,11]]
示例3
输入{1,2,3,4,5}
返回值[[1],[2,3],[4,5]]
示例4
输入{}
返回值[]
解题思路
要实现这一功能我们可以借助广度优先搜索BFS来逐层遍历二叉树。BFS 通常使用队列来实现。具体步骤如下
队列初始化首先将二叉树的根节点放入队列。逐层遍历循环遍历队列每次从队列中取出当前层的所有节点记录它们的值并将其左右子节点依次加入队列以便下一次循环遍历。存储每层节点在遍历每层节点时将当前层的节点值存入一个列表然后将这个列表添加到最终的结果二维数组中。处理空树的情况如果输入的树为空则返回一个空的结果数组。
代码实现
下面是使用 Java 实现的完整代码
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;public class Solution {public ArrayListArrayListInteger Print(TreeNode pRoot) {// 初始化一个二维数组来保存最终结果ArrayListArrayListInteger ret new ArrayList();// 初始化一个队列用于层序遍历QueueTreeNode queue new LinkedList();// 将根节点加入队列queue.add(pRoot);// 当队列不为空时继续进行遍历while (!queue.isEmpty()) {// 用于存储当前层的节点值ArrayListInteger list new ArrayList();// 当前层的节点数量int cnt queue.size();// 遍历当前层的所有节点while (cnt-- 0) {// 取出队列中的节点TreeNode node queue.poll();// 如果节点为空则跳过if (node null)continue;// 将节点的值加入当前层的列表list.add(node.val);// 将节点的左子节点加入队列queue.add(node.left);// 将节点的右子节点加入队列queue.add(node.right);}// 如果当前层有节点将其加入最终结果if (list.size() ! 0)ret.add(list);}// 返回最终结果return ret;}
}详细解析
Queue 数据结构我们使用 QueueTreeNode 来保存每一层的节点。在每一层开始时队列中包含了所有该层的节点。层序遍历通过 queue.size() 获取当前层的节点数量并使用一个循环来遍历这些节点。在遍历过程中将当前节点的左右子节点依次加入队列。结果存储每一层遍历完后我们将当前层的节点值列表 list 添加到结果数组 ret 中。边界条件如果 queue 中没有元素即队列为空时表示树已经遍历完毕退出循环。
总结
这个解法的核心是利用队列来实现二叉树的层序遍历。通过逐层记录节点值我们能够按照题目要求将每一层节点的值按行输出并最终返回一个包含多行的二维数组。该解法具有良好的时间和空间复杂度适用于题目要求的节点数量范围。
热门专栏推荐 想学习vue的可以看看这个
java基础合集
数据库合集
redis合集
nginx合集 linux合集
手写机制
微服务组件
spring_尘觉
springMVC
mybits
等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持
欢迎大家加入我的社区 尘觉社区 文章到这里就结束了如果有什么疑问的地方请指出诸佬们一起来评论区一起讨论 希望能和诸佬们一起努力今后我们一起观看感谢您的阅读 如果帮助到您不妨3连支持一下创造不易您们的支持是我的动力
