JavaScript遍历树结构:收集所有从根到叶子的路径数组

作者:木棉时间:2026-11-22 20:51:21浏览:272

深入讲解在JavaScript中遍历树结构并收集所有从根到叶子节点路径数组的高效实用方案。包含深度优先搜索回溯机制、纯函数传递、显式迭代栈实现及常见引用陷阱排查。

核心方案与即用代码

在前端业务与服务端逻辑中,树形数据随处可见,例如多级权限分类树、级联选择器(Cascader)、组织架构图以及路由层级结构。当我们需要生成面包屑导航链、导出所有可达分类组合或计算所有终端业务路径时,目标都是将非线性的树结构转换为一个二维数组,其中每个子数组表示一条从根节点开始、以叶子节点结束的完整节点序列。

我们先来看最标准、内存表现最好的基础实现:通过递归维护一个共享数组,并在叶子节点处固化路径。

/**
 * 收集树结构中从根到叶子节点的所有路径
 * @param {Object} root 树的根节点对象
 * @returns {Array<Array>} 路径二维数组
 */
function getAllRootToLeafPaths(root) {
  // 边界防护:空树直接返回空数组
  if (!root) return [];

  const result = [];
  const currentPath = [];

  function traverse(node) {
    // 1. 压入当前节点值(或节点本身 node)
    currentPath.push(node.val);

    // 2. 判断是否为叶子节点:无 children 或 children 为空数组
    const isLeaf = !node.children || node.children.length === 0;

    if (isLeaf) {
      // 命中叶子节点:存入当前路径的浅拷贝,避免后续回溯修改污染
      result.push([...currentPath]);
    } else {
      // 非叶子节点:递归遍历每一个子节点
      for (const child of node.children) {
        traverse(child);
      }
    }

    // 3. 回溯清理:从子分支返回时弹出当前节点,还原路径状态
    currentPath.pop();
  }

  traverse(root);
  return result;
}

给定包含分支与叶子的多叉树测试数据,执行该函数可以直观看到转换映射关系:

// 示例多叉树输入数据
const tree = {
  val: 'A',
  children: [
    {
      val: 'B',
      children: [
        { val: 'D', children: [] },
        { val: 'E' }
      ]
    },
    {
      val: 'C',
      children: [
        { val: 'F', children: [] }
      ]
    }
  ]
};

const paths = getAllRootToLeafPaths(tree);
console.log(paths);
// 示例输出结果:
// [
//   [ 'A', 'B', 'D' ],
//   [ 'A', 'B', 'E' ],
//   [ 'A', 'C', 'F' ]
// ]
JavaScript遍历树结构:收集所有从根到叶子的路径数组
图 1:原始多叉树结构与收集提取出的二维路径数组对应示意图

核心机制:叶子节点严谨判定与回溯时序

很多开发者在实现该算法时容易写出两个隐藏缺陷:一是叶子节点判断逻辑过于简陋,二是忽略了 JavaScript 对象引用的传递特性导致结果被洗空。理解以下两个核心机制,是写出高鲁棒性树遍历代码的前提。

1. 多叉树与二叉树的叶子节点判定差异

在严格二叉树(LeetCode 257 题等算法题场景)中,节点结构通常为 { val, left, right },因此叶子节点的充要判定条件是 !node.left && !node.right。

但在真实的 JavaScript 业务数据(如前端级联组件或后端接口返回的 JSON)中,树往往是多叉树,属性键通常为 children。此时叶子节点有三种常见的数据形态:

  • 完全缺少 children 属性(例如 undefined);
  • children 被显式赋值为 null;
  • children 存在但为一个空数组 []。
注意隐式类型转换陷阱

如果仅仅使用 if (!node.children) 来判断叶子节点,当节点带有空数组 children: [] 时,在 JavaScript 中 Boolean([]) === true,条件会判断为“非叶子”。随后代码进入 for (const child of node.children),由于数组长度为 0,循环根本不执行,结果导致该叶子节点既没有被记录到 result 中,也没有继续下潜,最终导致整条路径凭空消失。因此必须写成 !node.children || node.children.length === 0。

2. 为什么必须使用 [...currentPath] 浅拷贝?

在 JavaScript 中,数组属于引用类型(Reference Type)。变量 currentPath 存储的是内存堆中的数组地址。如果在遇到叶子节点时直接调用 result.push(currentPath),推入结果集的并不是该时刻数组的静态数据,而是对 currentPath 变量所指数组的引用。

当后续递归执行 pop() 回退状态,甚至整个树遍历完成将 currentPath 清空时,result 里面存放的每个元素引用的数组内容都会被同步修改。最终返回的 result 将变成包含多个空数组的错误结果 [[], [], []]。通过 [...currentPath] 或 currentPath.slice() 进行浅拷贝,可以在命中叶子节点的那一刻将数组切片固化,彻底隔绝后续回溯操作的副作用。

JavaScript遍历树结构:收集所有从根到叶子的路径数组
图 2:DFS 回溯执行过程中调用栈、共享路径数组与浅拷贝快照的时序演进图

操作步骤:标准 DFS 回溯算法实现流程

把树结构路径收集落实到代码上,可以拆解为五个清晰标准化的操作阶段:

  1. 步骤 01:前置安全防御(Guard Clause)
    检查输入的根节点 root 是否有效。若为 null 或 undefined,直接返回空结果集 [],避免后续访问 root.val 触发运行时报错。
  2. 步骤 02:当前节点入栈(Push State)
    在进入 traverse 函数体首部,立即把当前访问节点的特征值(例如 node.val 或完整 node)追加到 currentPath 的末尾。
  3. 步骤 03:分支判定(Branch Decision)
    通过 !node.children || node.children.length === 0 评估当前节点是否已达分支末端。
  4. 步骤 04A:叶子收敛(Snapshot Persistence)
    如果判定为叶子节点,当前 currentPath 正好完整记录了从根到达此叶子的全量链路,立即调用 result.push([...currentPath]) 截取快照。
  5. 步骤 04B:子树递归遍历(Subtree Recursion)
    若非叶子节点,迭代 node.children 数组,对每个子节点依次递归调用 traverse(child),继续向下延伸路径。
  6. 步骤 05:回溯清理(Backtrack Cleanup)
    在当前节点的全部子树处理完毕即将跳出函数之前,调用 currentPath.pop()。它将把当前节点从路径尾部移出,使调用上下文恢复到进入当前节点前的纯净状态。
JavaScript遍历树结构:收集所有从根到叶子的路径数组
图 3:树路径收集算法执行步骤决策流转图

实现范式对比:共享数组回溯、纯函数不可变与显式栈迭代

除了前文推荐的“共享数组 + 回溯”范式,根据团队代码规范与树的数据规模,还有另外两种常见的实现风格。不同方案在空间复杂度、垃圾回收(GC)开销和防爆栈能力上存在显著差异。

范式二:不可变纯函数传递(无副作用,适合轻量树)

纯函数式写法的特点是:每次向下递归时,直接把包含当前节点的新数组作为参数传递给下一层。由于每层都拥有自己独立的局部路径变量,因此不需要手动编写 pop() 回溯代码:

/**
 * 纯函数不可变参数传递实现
 */
function getPathsFunctional(node, currentPath = []) {
  if (!node) return [];

  // 每次递归直接通过展开运算符产生新数组
  const newPath = [...currentPath, node.val];
  const isLeaf = !node.children || node.children.length === 0;

  if (isLeaf) {
    return [newPath];
  }

  const result = [];
  for (const child of node.children) {
    result.push(...getPathsFunctional(child, newPath));
  }
  return result;
}

优劣分析:代码极短且无共享状态,非常符合 React / Redux 生态推崇的不可变数据习惯。但其缺陷在于:树如果包含 10,000 个节点,算法在递归下潜途中会频繁创建数万个短生命周期的临时数组,显著增加 V8 引擎年轻代(Young Generation)GC 回收压力。

范式三:显式栈迭代遍历(消除 JavaScript 调用栈溢出风险)

JavaScript 引擎(如 Chrome V8 或 Node.js)对递归调用栈的深度有严格上限(通常在 10,000 层左右)。当解析极其深邃的抽象语法树(AST)或层级特别深的链状树时,递归方案会抛出 RangeError: Maximum call stack size exceeded。

通过在堆内存中维护一个自定义的显式栈(Stack),将状态打包为 [node, currentPath] 压栈与出栈,可以彻底规避调用栈溢出问题:

/**
 * 显式栈迭代方式收集路径(抗深度爆栈方案)
 */
function getPathsIterative(root) {
  if (!root) return [];

  const result = [];
  // 显式栈存储元素结构:[当前节点, 到达该节点前累积的路径]
  const stack = [[root, [root.val]]];

  while (stack.length > 0) {
    const [currentNode, path] = stack.pop();
    const isLeaf = !currentNode.children || currentNode.children.length === 0;

    if (isLeaf) {
      result.push(path);
    } else {
      // 为保持与递归相同的前序访问顺序(左优先),子节点倒序入栈
      for (let i = currentNode.children.length - 1; i >= 0; i--) {
        const child = currentNode.children[i];
        stack.push([child, [...path, child.val]]);
      }
    }
  }

  return result;
}
JavaScript遍历树结构:收集所有从根到叶子的路径数组
图 4:共享数组回溯、纯函数传递与显式栈迭代三种范式的架构与内存对比图

生产环境进阶处理:异构键名、格式化与环引用防御

在企业级应用中,后端接口返回的树数据结构往往各不相同,例如有的使用 subList 代替 children,有的使用 code 代替 val;另外,某些复杂图结构转换不彻底时,节点可能存在循环引用(导致 DFS 进入死循环导致页面崩溃)。

以下是一个高度可配置、具备防御性编程的工业级通用封装:

/**
 * 通用树路径收集器(支持自定义属性键、格式化输出与环引用检测)
 * @param {Object} root 根节点
 * @param {Object} options 配置参数
 * @param {string} options.childrenKey 子节点数组键名,默认 'children'
 * @param {string|Function} options.valueExtractor 节点值提取器,默认提取 'val' 或 'id'
 * @param {boolean} options.formatString 是否格式化为字符串路径,如 'A > B > C'
 * @param {string} options.separator 路径字符串分隔符,默认 ' > '
 * @returns {Array<Array|string>}
 */
function collectTreePaths(root, options = {}) {
  const {
    childrenKey = 'children',
    valueExtractor = node => (node.val !== undefined ? node.val : node.id),
    formatString = false,
    separator = ' > '
  } = options;

  if (!root) return [];

  const result = [];
  const currentPath = [];
  // 防御环形引用:记录当前递归调用链中已经访问过的节点对象
  const visitedInPath = new Set();

  function traverse(node) {
    if (!node || typeof node !== 'object') return;

    // 环形引用检测:若当前调用栈已包含该节点,说明出现死循环链路,主动熔断
    if (visitedInPath.has(node)) {
      console.warn('[collectTreePaths] 检测到树结构中存在循环引用,已自动熔断当前路径', node);
      return;
    }

    visitedInPath.add(node);
    const nodeValue = typeof valueExtractor === 'function' ? valueExtractor(node) : node[valueExtractor];
    currentPath.push(nodeValue);

    const children = node[childrenKey];
    const isLeaf = !Array.isArray(children) || children.length === 0;

    if (isLeaf) {
      if (formatString) {
        result.push(currentPath.join(separator));
      } else {
        result.push([...currentPath]);
      }
    } else {
      for (const child of children) {
        traverse(child);
      }
    }

    // 回溯清理
    currentPath.pop();
    visitedInPath.delete(node);
  }

  traverse(root);
  return result;
}

特殊单节点树验证:当传入的树仅包含一个孤立根节点 { val: 'Root', children: [] } 时,该节点在执行到步骤 03 时即被识别为叶子节点,算法会正确输出 [['Root']],既不会死循环也不会丢失数据,符合边界预期。

实施自查清单与技术选型总结

核对维度 合格标准 不合规潜在故障
叶子判定条件 !node.children || node.children.length === 0 仅判 !node.children 会把 [] 当非叶子,导致漏掉整条叶子路径
路径快照隔离 result.push([...currentPath]) 或 slice() 直接存引用会导致数组元素在回溯完成后全部被清空为空数组 []
回溯时序配对 函数退出前执行 currentPath.pop() 漏写 pop() 会使后续分支残留前驱路径,产生杂糅脏数据
极端树深防御 树深 > 10,000 层时改用显式栈迭代方案 递归调用深度超限抛出 Maximum call stack size exceeded 崩溃
JavaScript遍历树结构:收集所有从根到叶子的路径数组
图 5:树路径遍历开发自查清单与业务场景技术选型导图
作者最新文章
相关文章
更多