如何递归搜索嵌套对象树中匹配标题的所有完整路径

如何递归搜索嵌套对象树中匹配标题的所有完整路径

本文介绍一种基于递归与栈结构的深度优先搜索方法，用于在具有层级关系的嵌套对象数组（如菜单树）中，精准定位所有 title 包含指定关键词（如 “line”）的节点，并返回其从根到匹配项的完整路径数组。

在构建导航菜单、权限路由或者内容目录时，我们常常会面对一种典型的数据结构：树。数据以嵌套对象数组的形式组织，每个节点都可能包含一个 `children` 数组，从而形成多级层级关系。这时候，如果我们需要根据标题进行模糊查找，并且要求返回的不是孤立的节点，而是从根节点到匹配节点的完整“家谱”，问题就变得有趣了。简单的扁平化遍历在这里会束手无策，关键在于，我们必须同步维护好“当前路径”这个上下文。

那么，如何优雅地解决这个问题呢？核心思路其实很清晰：利用一个显式的栈（stack）来动态记录从根节点到当前遍历节点的路径。在每次深入子节点前，将当前节点压入栈中；在回溯返回上一层前，再将其弹出。这样一来，栈内保存的，就始终是到达当前节点的完整路径。 再配合灵活的正则表达式进行匹配，无论是大小写不敏感，还是前缀、子串匹配，都能轻松实现。

下面就是基于这个思路的完整实现方案：

function searchAll(
  items: T[],
  search: RegExp
): T[][] {
  const stack: T[] = [];
  const results: T[][] = [];

  function tra verse(nodes: T[]): void {
    for (const node of nodes) {
      // 将当前节点加入路径栈
      stack.push(node);

      // 若标题匹配，保存当前完整路径（深拷贝避免引用污染）
      if (search.test(node.title)) {
        results.push(structuredClone(stack));
      }

      // 递归处理子节点
      if (Array.isArray(node.children) && node.children.length > 0) {
        tra verse(node.children);
      }

      // 回溯：退出当前节点，恢复上一层路径状态
      stack.pop();
    }
  }

  tra verse(items);
  return results;
}

使用示例

看看这个函数在实际中如何工作：

const result = searchAll(items, /line/i);
console.log(result);
// 输出三个路径数组，分别对应：
// /programs/program-line
// /blog/cars/cars-library/line-horizon
// /blog/cars/cars-library/lineup

需要留意的几个细节

当然，一个健壮的方案离不开对细节的把握。这里有几点值得特别注意：

• 深拷贝的选择：代码中使用了 `structuredClone` 来保存路径快照，这是现代浏览器和 Node.js 17+ 提供的安全方案。如果你的运行环境较旧，可以替换为 `JSON.parse(JSON.stringify(stack))`，但要注意，后者仅适用于纯数据对象，无法处理函数、Date、Map 等特殊类型。
• 性能表现：该算法的时间复杂度为 *O(n)*（n 为总节点数），需要遍历整棵树。空间复杂度在最坏情况下为 *O(h)*（h 是树的最大深度），这是深度优先搜索的典型特征。
• 搜索的灵活性：将 `search` 参数设计为正则表达式而非普通字符串，是一个关键设计。这为后续扩展打开了大门，比如使用 `/^line/i` 来匹配以 “line” 开头的标题，或者用 `/\bline\b/i` 来精确匹配整个单词。
• 结果的多样性：如果你需要的不是节点对象数组，而是扁平的路径字符串（例如 `‘/blog/cars/…’`），完全可以在保存结果前，通过 `stack.map(n => n.path).join(‘/’)` 来自行拼接，非常灵活。

总的来说，这个方案结构清晰、可读性强，并且天然支持任意深度的嵌套。它提供了一种处理树形数据层级搜索的通用范式，下次遇到类似需求时，不妨试试看。