JAVA练习45-二叉树的层序遍历

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

提示：这里可以添加本文要记录的大概内容：

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、题目·二叉树的层序遍历

1.题目描述

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

示例 1：

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

示例 2：

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

示例 3：

输入：root = []

输出：[]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.思路与代码

2.1 思路

1.创建一个Array类型数组用来输出，一个队列用来储存每层的结点

2.先判断树是否为空，若树为空，则输出空数组

3.遍历树，查找每层结点，放入一个新的数组中，遍历每层结点结束之后，将遍历到的结点加入输出的数组

4.输出数组

2.2 代码

代码如下（示例）：

/*** 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<>();//空树情况if(root == null){return res;}//队列储存Queue<TreeNode> q = new ArrayDeque<TreeNode>();q.add(root);while(!q.isEmpty()){//用来记录某一行ArrayList<Integer> row = new ArrayList(); int size = q.size();//因先进入的是根节点，故每层节点多少，队列大小就是多少for(int i = 0; i < size; i++){TreeNode cur = q.poll();row.add(cur.val);//若是左右孩子存在，则存入左右孩子作为下一个层次if(cur.left != null){q.add(cur.left);}     if(cur.right != null){q.add(cur.right);}}//每一层加入输出res.add(row);}return res;}
}

---

总结

提示：这里对文章进行总结：