102. 二叉树的层序遍历

难度: 中等

来源: 广度优先搜索

---

给你二叉树的根节点 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

/**
 * 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>> result = new ArrayList<List<Integer>>();
  if (root == null) { return result; }
  

  然后我们需要创建一个队列, 并把根节点root添加到队列中.

  Deque<TreeNode> deque = new ArrayDeque<>();
  deque.add(root);
  

  然后就是最重要的逻辑, 我们需要一边遍历当层的节点, 一边把下一层的节点添加到队列中. 这时候, 我们需要用 队列是否为空作为 遍历的整个停止条件.

  while(!deque.isEmpty()) {
      ...
  }
  

  然后就是那么一边抛出一边添加, 我们怎么知道当层的停止条件呢? 所以我们在当层遍历的开始时, 就需要判断当前队列中元素的长度, 然后当前层的停止条件就是这个长度.

  int levelLength = deque.size();
  

  然后, 我们一边从队列中抛出元素, 一边从抛出的元素添加其左右节点. 如下图所示.

  

  
  

  int levelLength = deque.size();
  List<Integer> level = new ArrayList<Integer>();
  for(int i = 0; i < levelLength; i++) {
      TreeNode node = deque.pop();
      level.add(node.val);
      if (node.left != null) deque.add(node.left);
      if (node.right != null) deque.add(node.right);
  }
  result.add(level);
  

  整体的解题思路如下所示.

  /**
  * 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>> result = new ArrayList<List<Integer>>();
          if (root == null) { return result; }
          Deque<TreeNode> deque = new ArrayDeque<>();
          deque.add(root);
          while(!deque.isEmpty()) {
              int levelLength = deque.size();
              List<Integer> level = new ArrayList<Integer>();
              for(int i = 0; i < levelLength; i++) {
                  TreeNode node = deque.pop();
                  level.add(node.val);
                  if (node.left != null) deque.add(node.left);
                  if (node.right != null) deque.add(node.right);
              }
              result.add(level);
          }
          return result;
      }
  }
  

  
  

  复杂度分析:

  • 时间复杂度: O(n²)
  • 空间复杂度: O(n)

  结果如下所示.