【二叉树】Leetcode 102. 二叉树的层序遍历【中等】

news/2024/5/9 5:54:23/文章来源:https://blog.csdn.net/FLGBgo/article/details/137072598

二叉树的层序遍历

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

示例1：

在这里插入图片描述
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

解题思路

层序遍历是一种按层次逐层遍历二叉树节点的方法，通常使用队列来实现。

1、创建一个队列，用于存储待访问的节点。
2、将根节点加入队列。
3、循环遍历队列，直到队列为空：
弹出队首节点，并将其值加入到结果列表中。
如果当前节点有左子节点，则将左子节点加入队列。
如果当前节点有右子节点，则将右子节点加入队列。
4、返回结果列表。

java实现

public class LevelOrderTraversal {static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}}public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) {return result;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {//当前层的节点数量int levelSize = queue.size();//存储当前层的节点的levelNodesList<Integer> levelNodes = new ArrayList<>();for (int i = 0; i < levelSize; i++) {//出队TreeNode current = queue.poll();//添加到对应层级的list中levelNodes.add(current.val);//利用栈的先进先出（FIFO）//对应测试案例的入栈后顺序为：3、9、20、5、15、17if (current.left != null) {queue.offer(current.left);}if (current.right != null) {queue.offer(current.right);}}result.add(levelNodes);}return result;}public static void main(String[] args) {// 构造一个二叉树TreeNode root = new TreeNode(3);root.left = new TreeNode(9);root.right = new TreeNode(20);root.left.left = new TreeNode(5);root.right.left = new TreeNode(15);root.right.right = new TreeNode(7);// 创建 LevelOrderTraversal 对象LevelOrderTraversal solution = new LevelOrderTraversal();// 进行层序遍历List<List<Integer>> result = solution.levelOrder(root);// 打印结果System.out.println("Level Order Traversal: " + result);}
}