LeetCode--HOT100题（41）

题目描述：102. 二叉树的层序遍历（中等）

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

LeetCode做题链接：LeetCode-二叉树的层序遍历

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

题目接口

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {}
}

解题思路

树的层序遍历可以用BFS，因为层序遍历要求的输入结果和BFS是不同的。层序遍历要求我们区分每一层，也就是返回一个二维数组。而BFS的遍历结果是一个一维数组，无法区分每一层。

思路如下：
1.创建一个空的结果列表res，这个列表用于存储每一层节点的值。
2.创建一个队列queue，并将根节点root加入队列。
3.当队列不为空时，执行以下操作：

• 获取当前队列的长度，即当前层的节点个数。
• 创建一个空的列表level，用于存储当前层的节点值。
• 遍历当前层的所有节点，对于每个节点，执行以下操作：
  • 从队列中取出一个节点，并把它的值加入到列表level中。
  • 如果这个节点有左子节点，那么将左子节点加入到队列中；如果这个节点有右子节点，那么将右子节点加入到队列中。
• 把列表level加入到结果列表res中。

4.最后返回结果列表res，这个列表中的每个元素都是一个列表，表示树的每一层的所有节点的值。

代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {// 创建一个二维列表，用于存储每一层的节点值List<List<Integer>> res = new ArrayList<>();// 创建一个队列，用于层序遍历Queue<TreeNode> queue = new ArrayDeque<>();// 如果根节点不为空，将其加入队列if (root != null) {queue.add(root);}// 当队列不为空时，进行循环while (!queue.isEmpty()) {// 获取当前层的节点个数int n = queue.size();// 创建一个列表，用于存储当前层的节点值List<Integer> level = new ArrayList<>();// 遍历当前层的每个节点for (int i = 0; i < n; i++) {// 取出队首节点TreeNode node = queue.poll();// 将节点值加入当前层的列表level.add(node.val);// 如果当前节点的左子节点不为空，将其加入队列if (node.left != null) {queue.add(node.left);}// 如果当前节点的右子节点不为空，将其加入队列if (node.right != null) {queue.add(node.right);}}// 将当前层的节点值列表加入结果列表res.add(level);}// 返回结果列表return res;}
}

成功！

PS:

感谢您的阅读！如果您觉得本篇文章对您有所帮助，请给予博主一个赞喔~