每日一题

题目信息

时间： 2019-06-25
题目链接：Leetcode
tag：二叉树队列广度优先搜索
难易程度：简单
题目描述：

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

示例1:

给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

提示

1.节点总数 <= 1000

解题思路

本题难点

题目要求的二叉树的 从上至下 打印（即按层打印），又称为二叉树的 广度优先搜索（BFS）

具体思路

BFS 通常借助队列的先入先出特性来实现。

每层打印到一行：将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。

代码

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
      //当根节点为空，则返回空列表 [] 
        if(root == null){
            return new ArrayList<>(0);
        }
      //打印结果列表 res = []
        List<List<Integer>> res = new ArrayList<>();
      //包含根节点的队列 queue = [root]
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
      //BFS 循环： 当队列 queue 为空时跳出
        while(!queue.isEmpty()){
          //新建一个临时列表 ans ，用于存储当前层打印结果
            List<Integer> ans = new ArrayList<>();
          //当前层打印循环： 循环次数为当前层节点数（即队列 queue 长度）；
            for(int i = queue.size(); i > 0; i--){
              //出队： 队首元素出队，记为 t
                TreeNode t = queue.poll();
              //打印： 将 t.val 添加至 ans 尾部
                ans.add(t.val);
              //添加子节点： 若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue 
                if(t.left != null){
                    queue.add(t.left);
                }
                if(t.right != null){
                    queue.add(t.right);
                }
            }
          //将当前层结果 tmp 添加入 res 
            res.add(ans);
        }
      //返回打印结果列表 res 即可
        return res;
    }
}

复杂度分析：

时间复杂度 O(N) ：N 为二叉树的节点数量，即 BFS 需循环 N 次。
空间复杂度 O(N) ：最差情况下，即当树为平衡二叉树时，最多有 N/2 个树节点同时在队列queue 中，使用 O(N) 大小的额外空间。

其他优秀解答

解题思路

一般在树相关的题目中都可以考虑递归解法

代码

class Solution {
  //输出结果列表res ，用于存储所有层的列表
    List<List<Integer>> res = new ArrayList();
    public List<List<Integer>> levelOrder(TreeNode root){
        //递归调用函数，从第0层开始
      	recur(root,0);
        return res;
    }
    public void recur(TreeNode root,int k){
        if(root != null){
          //如果列表层数小于二叉树的层数，新增当前层的列表
            if(res.size() <= k){
              		res.add(new ArrayList());
            }
          //将当前层的元素添加到当前层列表中   
            res.get(k).add(root.val);
          //递归调用二叉树的左子树，层数+1
            recur(root.left,k+1);
          //递归调用二叉树的右子树，层数+1
            recur(root.right,k+1);
        }
    }
}