LeetCode 429题：N叉树层序遍历报std::bad_alloc错误求助

问题描述 #

我在解决N叉树层序遍历问题时，编写了如下JavaScript代码：

var levelOrder = function(root) {
    let queue = [root, null];
    let result = [];
    let tmp = [];
    
    for(let i=0; i<queue.length; i++){
        let node = queue[i];
        
        if(!node){
            result.push(tmp);
            tmp = new Array();
            if(i !== queue.length-1) queue.push(null);
        }else{
             queue = [...queue, ...node.children];
            tmp.push(node.val);
        }
    }
    return result;
};

运行题目示例测试用例正常，但提交时出现std::bad_alloc错误。

错误原因 #

1. 内存爆炸式增长：每次处理节点时用queue = [...queue, ...node.children]重新赋值队列，这会创建新的数组副本。当处理大型N叉树时，数组副本会不断占用新内存，最终导致内存分配失败（std::bad_alloc本质是内存不足）。
2. 循环无法正确终止：for循环的i基于队列长度递增，但队列在循环中持续扩容，会导致循环遍历的节点数远超实际树节点数，进一步加剧内存消耗，甚至陷入无限循环。
3. 边界处理缺陷：若输入root为null，代码会返回包含空数组的结果[[]]，不符合题目要求（应返回空数组[]）。

修复方案 #

采用标记当前层长度的层序遍历方式，避免数组副本开销，同时精准控制每一层的节点处理：

var levelOrder = function(root) {
    if (!root) return [];
    const result = [];
    const queue = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);
            // 直接将子节点入队，无需创建数组副本
            if (node.children) {
                queue.push(...node.children);
            }
        }
        result.push(currentLevel);
    }
    return result;
};

修复要点 #

• 先判断root是否为null，直接返回空数组，处理边界情况。
• 使用while循环配合levelSize标记当前层节点数，无需用null做层分隔符，逻辑更清晰。
• 用queue.shift()取出队首节点，直接将子节点推入队列，避免创建数组副本，内存开销极低。
• 每一层处理完成后，将当前层结果加入最终数组，确保输出符合题目要求。

内容的提问来源于stack exchange，提问作者Varun Sukheja