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

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

🏠个人主页：尘觉主页

文章目录

😊把二叉树打印成多行
- 🥰题目描述
- - 数据范围
  - 要求
- 😋示例
- - 示例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 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;}
}