算法的学习笔记—把二叉树打印成多行(牛客JZ78)

😀前言
在算法面试中，二叉树的层序遍历是一个经典的题目。而这道题的要求是进一步将二叉树的每一层结点值打印成多行，即同一层结点从左至右输出，最终结果存放到一个二维数组中返回。接下来，我们将通过代码实例详细解析解题思路。

🏠个人主页：尘觉主页

😊把二叉树打印成多行

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 通常使用队列来实现。具体步骤如下：

1. 队列初始化：首先，将二叉树的根节点放入队列。
2. 逐层遍历：循环遍历队列，每次从队列中取出当前层的所有节点，记录它们的值，并将其左右子节点依次加入队列，以便下一次循环遍历。
3. 存储每层节点：在遍历每层节点时，将当前层的节点值存入一个列表，然后将这个列表添加到最终的结果二维数组中。
4. 处理空树的情况：如果输入的树为空，则返回一个空的结果数组。

😉代码实现

下面是使用 Java 实现的完整代码：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;public class Solution {public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {// 初始化一个二维数组来保存最终结果ArrayList<ArrayList<Integer>> ret = new ArrayList<>();// 初始化一个队列用于层序遍历Queue<TreeNode> queue = new LinkedList<>();// 将根节点加入队列queue.add(pRoot);// 当队列不为空时，继续进行遍历while (!queue.isEmpty()) {// 用于存储当前层的节点值ArrayList<Integer> 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;}
}

详细解析

1. Queue 数据结构：我们使用 Queue<TreeNode> 来保存每一层的节点。在每一层开始时，队列中包含了所有该层的节点。
2. 层序遍历：通过 queue.size() 获取当前层的节点数量，并使用一个循环来遍历这些节点。在遍历过程中，将当前节点的左右子节点依次加入队列。
3. 结果存储：每一层遍历完后，我们将当前层的节点值列表 list 添加到结果数组 ret 中。
4. 边界条件：如果 queue 中没有元素，即队列为空时，表示树已经遍历完毕，退出循环。

😄总结

这个解法的核心是利用队列来实现二叉树的层序遍历。通过逐层记录节点值，我们能够按照题目要求将每一层节点的值按行输出，并最终返回一个包含多行的二维数组。该解法具有良好的时间和空间复杂度，适用于题目要求的节点数量范围。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞