102. 二叉树的层序遍历

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

示例 1：

1
2
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

1
2
输入：root = [1]
输出：[[1]]

示例 3：

1
2
输入：root = []
输出：[]

提示：

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public List<List<Integer>> levelOrder(TreeNode root) {

    //结果数组
    List<List<Integer>> result = new ArrayList<List<Integer>>();

    //使用队列来辅助遍历
    Queue<TreeNode> que = new ArrayDeque<>();

    //根节点不为空，入队
    if (root != null) {
        que.offer(root);
    }

    //队列不为空时开始循环
    while (!que.isEmpty()) {
        //level用于存储每层节点的值
        ArrayList<Integer> level = new ArrayList<>();
        int len = que.size();


        while (len > 0) {
            //当前层的元素全部出队并存入当前层的集合中
            TreeNode node = que.poll();
            level.add(node.val);
            //当前节点的左孩子入队
            if (node.left != null) {
                que.offer(node.left);
            }
            //当前节点的右孩子入队
            if (node.right != null) {
                que.offer(node.right);
            }
            len--;
        }
        //遍历完一层就存入一层
        result.add(level);

    }
    //返回结果数组
    return result;
}
  • 时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)。
  • 空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n)。