# 102. 二叉树的层序遍历

# 题目描述

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

示例 1：

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

1
2

示例 2：

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

1
2

# 思路

前中后序递归遍历会先沿着一条分支走到底。现在要一层一层地走，应该用什么结构？队列先进先出，正好保证先入队的上一层节点先被处理，这也是代码随想录层序遍历的核心。

但题目还要求按层分组，怎样知道本层何时结束？每轮开始时保存 size = queue.size()，只弹出这 size 个节点。新入队的孩子留给下一轮。这里不能直接把不断变化的队列长度当作循环条件。

# 模拟过程

以 [3,9,20,null,null,15,7] 为例。先把 3 入队，第一轮取出 3，加入 [3]，并把 9、20 入队。第二轮固定 size = 2，取出 9、20，得到 [9,20]，同时把 15、7 入队。第三轮得到 [15,7]。

# 解题代码

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) return result;
        queue<TreeNode*> que;
        que.push(root);
        while (!que.empty()) {
            int size = que.size(); // 固定本层节点数，孩子留给下一层
            vector<int> level;
            for (int i = 0; i < size; ++i) {
                TreeNode* node = que.front();
                que.pop();
                level.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(level);
        }
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 复杂度分析

时间复杂度：O(n)，每个节点进出队列各一次。
空间复杂度：O(n)，队列在最宽一层可容纳 O(n) 个节点，输出另占 O(n)。

# 其他语言

# Python3

from collections import deque

class Solution:
    def levelOrder(self, root):
        if root is None:
            return []
        que, result = deque([root]), []
        while que:
            level = []
            for _ in range(len(que)):
                node = que.popleft()
                level.append(node.val)
                if node.left: que.append(node.left)
                if node.right: que.append(node.right)
            result.append(level)
        return result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# Java

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty()) {
            int size = que.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = que.poll();
                level.add(node.val);
                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
            }
            result.add(level);
        }
        return result;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# Go

func levelOrder(root *TreeNode) [][]int {
    result := [][]int{}
    if root == nil { return result }
    que := []*TreeNode{root}
    for len(que) > 0 {
        size := len(que)
        level := []int{}
        for i := 0; i < size; i++ {
            node := que[0]
            que = que[1:]
            level = append(level, node.Val)
            if node.Left != nil { que = append(que, node.Left) }
            if node.Right != nil { que = append(que, node.Right) }
        }
        result = append(result, level)
    }
    return result
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# JS

var levelOrder = function(root) {
    if (root === null) return [];
    const que = [root], result = [];
    let head = 0;
    while (head < que.length) {
        const end = que.length, level = [];
        while (head < end) {
            const node = que[head++];
            level.push(node.val);
            if (node.left) que.push(node.left);
            if (node.right) que.push(node.right);
        }
        result.push(level);
    }
    return result;
};