? ? ? ?这道题是我司小伙伴进公司面试遇到的一道题，也是力扣热题之一，难度中等，题目如下
? ? ? ?二叉树是常见的数据结构之一，一般我们遇到的都是二叉树的? 前序(先序) 中序 后续 这三种遍历方式，层序遍历就是一层一层的输出每一层节点的值，看返回的数据结构可知，一个list对象里面包含一个list对象，一个用来存放每一层的节点值，一个是所有层的节点值。
? ? ? ? 层序遍历思路理解:? 用两个linkedlist对象，存在树的节点，一个是树的头节点，一个是树的左右节点, 每次取头节点放到 list 对象中，头节点获取完毕后，再把树的左右节点赋值给头节点，再次进行遍历，比如以下树:?
首先头节点? ?queue1? 有完整的树 （1,3,5,7,9,11,13）第一次循环，把 1放到 list中?queue2 中有两颗树 （3,7,9 | 5,11,13）tmp 等于 queue1 等于空 ，queue1 等于?queue2?（3,7,9 | 5,11,13）?queue2?等于?tmp 等于空。
第二次循环， queue1?中有两颗树 （3,7,9 | 5,11,13）内层while循环 第一次 取出 3?放到 list中?queue2 放入两棵树（7 9）第二次 取出 5?放到 list中?queue2 放入两棵树（11 13），此时queue2 中有四颗树 （7? 9 11 13）tmp 等于 queue1 等于空 ，queue1 等于?queue2?（7? 9 11 13）?queue2?等于?tmp 等于空。
第三次循环， queue1 中有四颗树 （7 9 11 13）内层while循环 第一次 取出 7?放到 list中， queue1 7 没有左右节点，因此 queue2 还是空，内层第二次 取出 9?放到 list中，同样queue1 9 没有左右节点，因此 queue2 还是空，内层第三次 取出 11 放到 list中，同样queue1 11 没有左右节点，因此 queue2 还是空，内层第四次 取出 13 放到 list中，同样queue1 13?没有左右节点，因此 queue2 还是空，tmp 等于 queue1 等于空 ，queue1 等于?queue1?等于空? queue1?等于?tmp 等于空。
第四次循环?queue1 为空结束，每一次循环的一个list数组就是一层数据，这样既可
?
package com.example.demo.test;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
* @author qiankun.hu
* @version 1.0.0
* @createTime 2021年12月09日 11:23:00
* @Description 树的层序输出
*/
public class Tree {
public static void main(String[] args) {
TreeNode t4 = new TreeNode(7);
TreeNode t5 = new TreeNode(9);
TreeNode t2 = new TreeNode(3,t4,null);
TreeNode t3 = new TreeNode(5,t5,null);
TreeNode t1 = new TreeNode(1,t2,t3);
levelOrder(t1);
}
/**
* 层序遍历
* @param root
* @return
*/
public static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root==null)
return res;
LinkedList<TreeNode> queue1 = new LinkedList<>(),queue2 = new LinkedList<>();
queue1.offer(root);
while (!queue1.isEmpty()){
List<Integer> item = new ArrayList<>();
while (!queue1.isEmpty()){
TreeNode node = queue1.remove();
item.add(node.val);
if (node.left!=null)
queue2.offer(node.left);
if (node.right!=null)
queue2.offer(node.right);
}
res.add(item);
LinkedList<TreeNode> tmp = queue1;
queue1 = queue2;
queue2 = tmp;
}
return res;
}
static 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;
}
}
}
解题代码来自力扣评论区