代码随想录-45-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

1.使用队列

思路（定义变量）

• ArrayDeque作为队列
• 封装结果的List

通解思路

略

2. 本题思路分析：

将当前在队列中的元素的val封装到结果中，并将其左右孩子压入到队列。
设置两层循环，最外层是判断当队列不为空继续循环，
内层循环，在内层循环前记录当前队列长度，作为当前层的节点个数，作为内层循环的的循环次数。

3. 算法实现

• 代码：
  统一的树节点类

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> results = new ArrayList<List<Integer>>();
    if(root == null){
        return results;
    }
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int size = queue.size();            
        List<Integer> result = new ArrayList<>();
        for(int i = 0;i < size;i++){
            TreeNode cur = queue.remove();
            result.add(cur.val);
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
        results.add(result);
    }
    return results;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

4. pop函数的算法复杂度

时间复杂度：O(n)
空间复杂度：O(n)

5. 算法坑点

1. 内层循环开始前，记录当前队列元素的长度，此长度代表当前层的树节点的数量。