JS递归处理多维数组：筛选选中项及其父节点（栈溢出问题）

我们需要处理一个嵌套的分类数组（每个节点包含childCategories子数组），核心需求是筛选出所有选中项及其所有父节点。当前实现的递归代码在单选场景下工作正常，但多选（比如同时选中节点C和D）时，会触发Maximum call stack size exceeded栈溢出错误。

问题原因分析 #

栈溢出通常源于递归逻辑的无限循环或调用栈深度超限，多选场景下的常见诱因：

• 递归处理多个选中项时，重复对同一父节点发起递归调用，导致调用栈持续累积
• 递归函数未设置有效终止条件，或终止条件在多选场景下失效
• 未记录已处理节点，导致同一节点被反复触发递归

解决方案 #

方案1：迭代法（无栈溢出风险，推荐） #

思路：先遍历整个分类树收集所有选中项的完整路径（从根到选中节点的父节点链），再基于这些路径构建最终的筛选树，确保每个节点仅被处理一次。

function filterSelectedCategoriesWithParents(categories, selectedIds) {
  // 收集所有选中项的完整路径
  const selectedPaths = [];
  const stack = [...categories.map(cat => ({ node: cat, path: [cat.id] }))];

  while (stack.length > 0) {
    const { node, path } = stack.pop();
    if (selectedIds.includes(node.id)) {
      selectedPaths.push([...path]);
    }
    if (node.childCategories?.length) {
      stack.push(...node.childCategories.map(child => ({
        node: child,
        path: [...path, child.id]
      })));
    }
  }

  // 构建筛选后的分类树
  const result = [];
  const nodeMap = new Map();

  // 存入所有涉及的节点
  function traverseAndAdd(node) {
    if (selectedPaths.some(path => path.includes(node.id))) {
      nodeMap.set(node.id, { ...node, childCategories: [] });
      node.childCategories?.forEach(traverseAndAdd);
    }
  }
  categories.forEach(traverseAndAdd);

  // 关联父子节点关系
  function buildTree(node) {
    const mappedNode = nodeMap.get(node.id);
    if (mappedNode) {
      const parentPath = selectedPaths.find(p => p.includes(node.id))?.slice(0, -1);
      if (parentPath?.length) {
        const parentNode = nodeMap.get(parentPath.at(-1));
        parentNode?.childCategories.push(mappedNode);
      } else {
        result.push(mappedNode);
      }
      node.childCategories?.forEach(buildTree);
    }
  }
  categories.forEach(buildTree);

  return result;
}

方案2：优化递归（加缓存避免重复调用） #

思路：给递归函数添加processedIds集合，记录已处理的节点ID，避免对同一节点重复发起递归调用，从根源上防止栈溢出。

function filterSelectedCategoriesWithParents(categories, selectedIds, processedIds = new Set()) {
  const filtered = [];

  for (const category of categories) {
    if (processedIds.has(category.id)) continue;

    const hasSelectedChild = category.childCategories?.length 
      ? filterSelectedCategoriesWithParents(category.childCategories, selectedIds, processedIds).length > 0
      : false;

    if (selectedIds.includes(category.id) || hasSelectedChild) {
      processedIds.add(category.id);
      filtered.push({
        ...category,
        childCategories: filterSelectedCategoriesWithParents(category.childCategories, selectedIds, processedIds)
      });
    }
  }

  return filtered;
}

• 方案1完全规避递归，适合层级极深的分类树场景
• 方案2代码更简洁，通过缓存解决重复调用问题，适合层级适中的分类结构

内容的提问来源于stack exchange，提问作者Ben jamin