LeetCode 第429题：N叉树的层序遍历

📖 文章摘要

本文详细解析LeetCode第429题“N叉树的层序遍历”，这是一道考察树结构层序遍历的问题。文章提供了基于队列的BFS解题思路，包含C#、Python、C++三种语言实现，配有详细的分析和性能对比。适合想要提升树结构操作和广度优先搜索能力的程序员。

核心知识点： N叉树、层序遍历、队列
难度等级： 中等
推荐人群： 具有基础数据结构知识的程序员

题目描述

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]
解释：
    1
  / | \
 3  2  4
/ \
5  6

示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

提示

树的高度不会超过 1000
树的节点总数在 [0, 10^4] 之间

解题思路

本题可以使用广度优先搜索（BFS）来实现层序遍历，主要步骤如下：

使用队列存储每一层的节点：
- 初始时将根节点入队
- 每次处理一整层的节点
处理每一层的节点：
- 记录当前层的节点数量
- 依次处理该层所有节点
- 将子节点加入队列
收集结果：
- 每层的节点值存入一个数组
- 所有层的数组组成最终结果

图解思路

层序遍历过程

步骤	操作	结果	说明
初始状态	根节点入队	[1]	第一层
处理第一层	子节点入队	[3,2,4]	第二层
处理第二层	子节点入队	[5,6]	第三层
完成遍历	收集结果	[[1],[3,2,4],[5,6]]	最终结果

队列状态变化

阶段	队列内容	当前层结果	说明
开始	[1]	[1]	根节点
第一层后	[3,2,4]	[3,2,4]	第二层节点
第二层后	[5,6]	[5,6]	第三层节点
结束	[]	完成	遍历结束

代码实现

C# 实现

public class Solution {
    public IList<IList<int>> LevelOrder(Node root) {
        IList<IList<int>> result = new List<IList<int>>();
        if (root == null) return result;
        
        Queue<Node> queue = new Queue<Node>();
        queue.Enqueue(root);
        
        while (queue.Count > 0) {
            int levelSize = queue.Count;
            List<int> currentLevel = new List<int>();
            
            // 处理当前层的所有节点
            for (int i = 0; i < levelSize; i++) {
                Node node = queue.Dequeue();
                currentLevel.Add(node.val);
                
                // 将所有子节点加入队列
                foreach (var child in node.children) {
                    queue.Enqueue(child);
                }
            }
            
            result.Add(currentLevel);
        }
        
        return result;
    }
}

Python 实现

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root:
            return []
        
        result = []
        queue = deque([root])
        
        while queue:
            level_size = len(queue)
            current_level = []
            
            # 处理当前层的所有节点
            for _ in range(level_size):
                node = queue.popleft()
                current_level.append(node.val)
                
                # 将所有子节点加入队列
                queue.extend(node.children)
            
            result.append(current_level)
        
        return result

C++ 实现

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> result;
        if (!root) return result;
        
        queue<Node*> q;
        q.push(root);
        
        while (!q.empty()) {
            int levelSize = q.size();
            vector<int> currentLevel;
            
            // 处理当前层的所有节点
            for (int i = 0; i < levelSize; i++) {
                Node* node = q.front();
                q.pop();
                currentLevel.push_back(node->val);
                
                // 将所有子节点加入队列
                for (Node* child : node->children) {
                    q.push(child);
                }
            }
            
            result.push_back(currentLevel);
        }
        
        return result;
    }
};

执行结果

C# 实现

执行用时：248 ms
内存消耗：42.8 MB

Python 实现

执行用时：52 ms
内存消耗：16.4 MB

C++ 实现

执行用时：20 ms
内存消耗：11.8 MB

性能对比

语言	执行用时	内存消耗	特点
C#	248 ms	42.8 MB	实现清晰但性能较差
Python	52 ms	16.4 MB	代码简洁，性能中等
C++	20 ms	11.8 MB	性能最优

代码亮点

🎯 使用队列实现层序遍历
💡 每次处理整层节点
🔍 高效的内存管理
🎨 代码结构清晰，易于理解

常见错误分析

🚫 忘记处理空树情况
🚫 未正确处理层级信息
🚫 队列使用不当
🚫 内存管理不当（C++）

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
BFS	O(n)	O(w)	实现简单，直观	需要额外空间
DFS	O(n)	O(h)	空间复杂度较低	需要额外处理层级信息

其中：

n 是节点总数
w 是树的最大宽度
h 是树的高度

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第429题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

图解思路

层序遍历过程

队列状态变化

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流