LeetCode 102. 二叉树的层序遍历

Categories:

Tags:

题目描述
思路分析
1. 解法一：BFS（队列 + 层快照）（推荐）
2. 解法二：DFS（递归按层收集）
相似题目

题目描述

✅ 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

考察公司：美团

思路分析

解法一：BFS（队列 + 层快照）（推荐）

核心思路：

使用队列做层序遍历。

每层开始时记录当前队列长度 size，只弹出 size 个节点，保证层与层之间不会混淆。

依次收集本层节点值，并将左右子节点入队。

复杂度分析：

时间复杂度：O(n)，其中 n 表示二叉树节点数。

空间复杂度：O(n)，其中 n 表示队列最宽层的节点数。

// BFS 按层遍历
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            res.add(level);
        }

        return res;
    }
}

// BFS 按层遍历
func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}

	var res [][]int
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		size := len(queue)
		level := make([]int, 0, size)

		for i := 0; i < size; i++ {
			node := queue[0]
			queue = queue[1:]
			level = append(level, node.Val)

			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}

		res = append(res, level)
	}

	return res
}

解法二：DFS（递归按层收集）

核心思路：

用递归遍历节点，并带上当前层 depth。

当 depth == res.size() 时新增一层列表。

将当前节点值追加到对应层，再递归左右子树。

复杂度分析：

时间复杂度：O(n)，其中 n 表示二叉树节点数。

空间复杂度：O(n)，其中 n 表示递归栈深度与结果集合规模。

// DFS 按层收集
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, 0, res);
        return res;
    }

    private void dfs(TreeNode node, int depth, List<List<Integer>> res) {
        if (node == null) {
            return;
        }

        if (depth == res.size()) {
            res.add(new ArrayList<>());
        }

        res.get(depth).add(node.val);
        dfs(node.left, depth + 1, res);
        dfs(node.right, depth + 1, res);
    }
}

// DFS 按层收集
func levelOrder(root *TreeNode) [][]int {
	var res [][]int
	dfsLevel(root, 0, &res)
	return res
}

func dfsLevel(node *TreeNode, depth int, res *[][]int) {
	if node == nil {
		return
	}

	if depth == len(*res) {
		*res = append(*res, []int{})
	}

	(*res)[depth] = append((*res)[depth], node.Val)
	dfsLevel(node.Left, depth+1, res)
	dfsLevel(node.Right, depth+1, res)
}

相似题目

题目	难度	考察点
103. 二叉树的锯齿形层序遍历	中等	BFS、队列
107. 二叉树的层序遍历 II	中等	BFS
111. 二叉树的最小深度	简单	BFS、DFS
314. 二叉树的垂直遍历	中等	BFS、哈希表
637. 二叉树的层平均值	简单	BFS
429. N 叉树的层序遍历	中等	BFS
993. 二叉树的堂兄弟节点	简单	BFS、DFS
2471. 逐层排序二叉树所需的最少操作数目	中等	BFS、置换环
2493. 将节点分成尽可能多的组	困难	BFS、图论
199. 二叉树的右视图	中等	BFS、DFS
515. 在每个树行中找最大值	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/87203213