力扣算法Java常见面试题之二叉树的层序遍历，力扣算法学习之路

偏执的太偏执、 2023-10-02 17:17 3阅读 0赞

这道题是我司小伙伴进公司面试遇到的一道题，也是力扣热题之一，难度中等，题目如下

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA6Z2T5Z2k5LiK5rW35YiG5Z2k_size_20_color_FFFFFF_t_70_g_se_x_16][]

二叉树是常见的数据结构之一，一般我们遇到的都是二叉树的 前序(先序) 中序 后续 这三种遍历方式，层序遍历就是一层一层的输出每一层节点的值，看返回的数据结构可知，一个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数组就是一层数据，这样既可**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA6Z2T5Z2k5LiK5rW35YiG5Z2k_size_19_color_FFFFFF_t_70_g_se_x_16][]

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;
         }
      }
    
    }

解题代码来自力扣评论区

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA6Z2T5Z2k5LiK5rW35YiG5Z2k_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/2b23831d728e478cba67d8cbf778bad3.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6Z2T5Z2k5LiK5rW35YiG5Z2k,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA6Z2T5Z2k5LiK5rW35YiG5Z2k_size_19_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/f451e3f71e03464f896db9fd57b15830.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6Z2T5Z2k5LiK5rW35YiG5Z2k,size_19,color_FFFFFF,t_70,g_se,x_16