二叉树的层序遍历

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

二叉树的层序遍历 - 图1

模板

  1.   /**
  2.      * BFS遍历（借助队列）
  3.      *
  4.      * @param root
  5.      * @return
  6.      */
  7. public List<List<Integer>> levelOrder(TreeNode root) {
  8.     Queue<TreeNode> queue = new LinkedList<>(); // 辅助队列进行BFS遍历
  9.     List<List<Integer>> res = new ArrayList<>();
  11.     if (root == null) {
  12.         return res;
  13.     }
  15.     queue.offer(root);
  17.     while (!queue.isEmpty()) {
  18.         List<Integer> list = new ArrayList<>();
  19.         int len = queue.size(); // 每一层的大小
  21.         while (len > 0) {   // 遍历该层的元素
  22.             TreeNode node = queue.poll();   // 当前层次的元素
  23.             list.add(node.val); // 取出这一层的元素出队
  25.             // 将下一层的元素入队
  26.             if (node.left != null) queue.offer(node.left);
  27.             if (node.right != null) queue.offer(node.right);
  28.             len--;  // 此时该层元素已经出队，数量减一
  29.         }
  30.         res.add(list);
  31.     }
  33.     return res;
  34.     }
  35. }

此模板的核心思路应对很多题不需要改变，根据情况变通即可。

模板解决其他题目

可以使用此模板解决以下类似题：

  • 102.二叉树的层序遍历
  • 107.二叉树的层次遍历II（从下往上遍历的话，只需要从上往下层次遍历，再将结果反转即可）
  • 199.二叉树的右视图（每层取最后一个元素即可）
  • 637.二叉树的层平均值 (每行求平均值即可)
  • 429.N叉树的层序遍历（N叉树节点使用List存放，左右节点入队修改为遍历List，每个节点入队即可）
  • 515.在每个树行中找最大值 (每行求最大值即可)
  • 116.填充每个节点的下一个右侧节点指针（每层前一个指针指向后一个指针即可）
  • 117.填充每个节点的下一个右侧节点指针II（不完整二叉树也是一致思路，因为队列入队是不入null节点，每层前一个指针指向后一个指针即可）
  • 104.二叉树的最大深度（遍历一层深度加一即可）
  • 111.二叉树的最小深度（遍历每层，深度加一，遇到左右节点都为空直接返回深度即可）