# 二叉树的层序遍历

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

示例 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

# 题目要求分析：

对二叉树进行一个层序遍历，顺序是一层一层的遍历

	   1
	 /   \
	2		 3
  /  \   /   \
 4		5 6	  7

从最顶层的数据节点也就是 1

1

然后就是第二层的节点

1	2	3

然后就是第三层，有四个数据节点

1	2	3	4	5	6	7

也就是说，我们遍历二叉树的顺序是按一层一层来的，将来遍历出来的应该就是 1, 2, 3, 4, 5, 6, 7。这叫层序遍历

# 思路分析：

	   1
	 /   \
	2		 3
  /  \   /   \
 4		5 6	  7
 
 # 我们可以设定一个队列
 头[]尾
 # 我们可以把第一层 根节点 加入到 队列里面去
 头[1]尾
 # 每次 从 队列 里 获取一个元素 
 1 # 把刚才的1 弹出，判断1是否有左右孩子，如果有比如说 左孩子2 那么就加入到队列里，右孩子3也加入到队列里面去
 头[2, 3]尾 # 此时队列里面存储了 第二层的数据
 # 此时 第一层的数据 已经遍历完了
 # 遍历第二层的数据，将队列 头部的 元素 弹出来
 1 2 # 把2 弹出，判断2是否有左右孩子，有就加入到队列里面
 头[3, 4, 5]尾 # 第三层的左半个节点就添加完了，重复这个过程
 1 2 3 # 把3 弹出， 判断是否有 左右孩子，有就加入到队列里面
 头[5, 6, 7]尾 # 第三层的右半个节点就添加完了，重复这个过程
 1 2 3 4 # 弹出4 判断是否有左右孩子，判断没有了，队列中就不需要加入节点了
 头[6, 7]尾
 1 2 3 4 5 # 弹出5 判断是否有左右孩子，判断没有了，队列中就不需要加入节点了
 头[7]尾
 1 2 3 4 5 6 # 弹出6 判断是否有左右孩子，判断没有了，队列中就不需要加入节点了
 头[]尾
 1 2 3 4 5 7 # 弹出7 判断是否有左右孩子，判断没有了，队列中就不需要加入节点了

• 我们已知 第一个节点 是 root 节点 根节点，那么下面几层呢 都需要间接的获得

# 代码：

public List<List<Integer>> levelOrder(TreeNode root) {

      List<List<Integer>> res = new ArrayList<>();

      Queue<TreeNode> queue = new ArrayDeque<>();

      if(root != null)

      {

      queue.add(root);

      }

      int c1 = 1;

      while(! queue.isEmpty())

      {

        int c2 = 0;

        List<Integer> list = new ArrayList<>();

        for(int i = 0; i < c1; i++)

        {

          TreeNode node = queue.poll();

          list.add(node.val);

          if(node.left != null)

          {

            queue.add(node.left);

            c2++;

          }

          if(node.right != null)

          {

            queue.add(node.right);

            c2++;

          }

        }

        c1 = c2;

        res.add(list);

      }

      return res;

    }

# leetcode 中 精选 题解 分享

leetcode 中 精选 的 解题 分享：

分享地址 https://leetcode.cn/problems/binary-tree-level-order-traversal/solutions/244853/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/

# 解题思路

本文将会讲解为什么这道题适合用广度优先搜索（BFS），以及 BFS 适用于什么样的场景。

DFS（深度优先搜索）和 BFS（广度优先搜索）就像孪生兄弟，提到一个总是想起另一个。然而在实际使用中，我们用 DFS 的时候远远多于 BFS。那么，是不是 BFS 就没有什么用呢？

如果我们使用 DFS/BFS 只是为了遍历一棵树、一张图上的所有结点的话，那么 DFS 和 BFS 的能力没什么差别，我们当然更倾向于更方便写、空间复杂度更低的 DFS 遍历。不过，某些使用场景是 DFS 做不到的，只能使用 BFS 遍历。这就是本文要介绍的两个场景：「层序遍历」、「最短路径」。

本文包括以下内容：

DFS 与 BFS 的特点比较
BFS 的适用场景
如何用 BFS 进行层序遍历
如何用 BFS 求解最短路径问题
DFS 与 BFS
让我们先看看在二叉树上进行 DFS 遍历和 BFS 遍历的代码比较。

DFS 遍历使用 递归：

void dfs(TreeNode root) {

    if (root == null) {

        return;

    }

    dfs(root.left);

    dfs(root.right);

}

BFS 遍历使用队列数据结构：

void bfs(TreeNode root) {

    Queue<TreeNode> queue = new ArrayDeque<>();

    queue.add(root);

    while (!queue.isEmpty()) {

        TreeNode node = queue.poll(); // Java 的 pop 写作 poll ()

        if (node.left != null) {

            queue.add(node.left);

        }

        if (node.right != null) {

            queue.add(node.right);

        }

    }

}

只是比较两段代码的话，最直观的感受就是：DFS 遍历的代码比 BFS 简洁太多了！这是因为递归的方式隐含地使用了系统的 栈，我们不需要自己维护一个数据结构。如果只是简单地将二叉树遍历一遍，那么 DFS 显然是更方便的选择。

虽然 DFS 与 BFS 都是将二叉树的所有结点遍历了一遍，但它们遍历结点的顺序不同

这个遍历顺序也是 BFS 能够用来解「层序遍历」、「最短路径」问题的根本原因。下面，我们结合几道例题来讲讲 BFS 是如何求解层序遍历和最短路径问题的。

BFS 的应用一：层序遍历
BFS 的层序遍历应用就是本题了：

LeetCode 102. Binary Tree Level Order Traversal 二叉树的层序遍历（Medium）

给定一个二叉树，返回其按层序遍历得到的节点值。 层序遍历即逐层地、从左到右访问所有结点。

什么是层序遍历呢？简单来说，层序遍历就是把二叉树分层，然后每一层从左到右遍历

乍一看来，这个遍历顺序和 BFS 是一样的，我们可以直接用 BFS 得出层序遍历结果。然而，层序遍历要求的输入结果和 BFS 是不同的。层序遍历要求我们区分每一层，也就是返回一个二维数组。而 BFS 的遍历结果是一个一维数组，无法区分每一层。

那么，怎么给 BFS 遍历的结果分层呢？我们首先来观察一下 BFS 遍历的过程中，结点进队列和出队列的过程：

截取 BFS 遍历过程中的某个时刻

可以看到，此时队列中的结点是 3、4、5，分别来自第 1 层和第 2 层。这个时候，第 1 层的结点还没出完，第 2 层的结点就进来了，而且两层的结点在队列中紧挨在一起，我们 无法区分队列中的结点来自哪一层。

因此，我们需要稍微修改一下代码，在每一层遍历开始前，先记录队列中的结点数量 n（也就是这一层的结点数量），然后一口气处理完这一层的 n 个结点

// 二叉树的层序遍历

void bfs(TreeNode root) {

    Queue<TreeNode> queue = new ArrayDeque<>();

    queue.add(root);

    while (!queue.isEmpty()) {

        int n = queue.size();

        for (int i = 0; i < n; i++) { 

            // 变量 i 无实际意义，只是为了循环 n 次

            TreeNode node = queue.poll();

            if (node.left != null) {

                queue.add(node.left);

            }

            if (node.right != null) {

                queue.add(node.right);

            }

        }

    }

}

这样，我们就将 BFS 遍历改造成了层序遍历。在遍历的过程中，结点进队列和出队列的过程为

可以看到，在 while 循环的每一轮中，都是将当前层的所有结点出队列，再将下一层的所有结点入队列，这样就实现了层序遍历

最终我们得到的题解代码为:

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;

}