JavaScript实现二叉树层序遍历：递归与队列两种解法

Ada

发布时间：2026-10-15| 6人浏览过

原创

本文详解JavaScript中二叉树层序遍历的两种核心实现方式：基于递归的深度优先搜索和基于队列的广度优先搜索。通过代码片段与逻辑推演，展示如何按层从左至右收集节点值，涵盖空树处理、层级归组及迭代循环的关键步骤。

题目目标与示例

层序遍历要求逐层地、从左到右访问二叉树的所有节点。对于给定的二叉树结构，输出应为嵌套数组，每一层包含该层所有节点的值。若根节点为空，则返回空数组。

以如下二叉树为例：

其正确的层序遍历结果应为：

方法一：递归实现（DFS）

第1步：定义递归函数与状态变量

外层函数负责初始化结果容器并调用递归入口。使用一个全局变量 deep 记录当前节点的深度，用于确定当前节点应放入结果数组的第几层。

var levelOrder = function(root) {
    if (root === null) return []
    let result = [];
    let deep = 0;
    
    // 内部递归函数
    function recursion(node) {
        if (!node) return;
        
        deep++;
        // 如果当前层级数组不存在，则创建；否则追加元素
        if (result[deep - 1]) {
            result[deep - 1].push(node.val);
        } else {
            result[deep - 1] = [node.val];
        }
        
        // 递归左子树
        recursion(node.left);
        // 递归右子树
        recursion(node.right);
        
        deep--;
    }

    recursion(root);
    return result;
};

第2步：解析递归逻辑流程

深度管理：进入节点时 deep 加一，退出时减一，确保回溯后回到父节点所在的层级。
数据归组：result[deep - 1] 对应当前层级的数组。利用 push 将同层节点依次加入。
边界判断：先判断当前节点是否为 null，避免无效指针引发的报错。

注意：虽然此方法能正确输出层级结果，但严格意义上属于深度优先搜索（DFS）。标准层面的“层序遍历”通常指广度优先搜索（BFS）。

方法二：队列实现（BFS）

这是解决层序遍历最经典且标准的做法，利用队列（Queue）“先进先出”的特性，一层一层地向外扩展。

第3步：构建队列迭代框架

初始化队列放入根节点。使用两个辅助数组：res 暂存当前层的节点值，items 暂存下一层的子节点。当当前层遍历完（队列为空），将暂存的下一层节点回写进队列。

var levelOrder = function(root) {
    let result = [];
    if (!root) return result;
    
    let queue = [root]; // 初始队列包含根节点
    let res = [];       // 当前层结果
    let items = [];     // 下一层节点暂存

    while (queue.length > 0 || items.length > 0) {
        // 1. 处理队列中的节点
        let nowRoot = queue.shift(); // 取出队首节点
        
        if (nowRoot) {
            res.push(nowRoot.val);   // 收集当前层值
            items.push(nowRoot.left); // 收集左子节点
            items.push(nowRoot.right);// 收集右子节点
        }

        // 2. 检查当前层是否完成
        if (queue.length === 0) {
            // 如果当前层还有未处理的子节点（items不为空）
            if (items.length > 0) {
                result.push(res);          // 保存当前层结果
                queue = items;             // 切换到下一层
                items = [];                // 清空暂存
                res = [];                  // 重置当前层集合
            } else {
                // items为空说明没有子节点了，本次层已完全结束
                break;
            }
        }
    }
    return result;
};