从嵌套数组构建祖先列表

基础概念

嵌套数组是指数组中的元素也是数组，这种结构常用于表示层次关系，如文件系统、组织结构等。构建祖先列表就是将这种层次关系转换为一个扁平的列表，其中每个元素包含其所有祖先的信息。

类型

构建祖先列表的方法主要有递归和迭代两种。

应用场景

文件系统管理：在文件系统中，文件和目录通常以嵌套数组的形式存储，构建祖先列表有助于快速查找文件的路径。
组织结构管理：在组织结构中，员工和部门的关系可以用嵌套数组表示，构建祖先列表有助于查询员工的上下级关系。
路由管理：在Web开发中，路由结构通常也是嵌套的，构建祖先列表有助于生成面包屑导航。

示例代码

以下是一个使用递归方法从嵌套数组构建祖先列表的示例代码：

function buildAncestors(nestedArray) {
  let ancestors = [];

  function traverse(arr, currentPath) {
    arr.forEach(item => {
      let newPath = currentPath.concat(item.id);
      ancestors.push(newPath);
      if (item.children) {
        traverse(item.children, newPath);
      }
    });
  }

  traverse(nestedArray, []);
  return ancestors;
}

// 示例嵌套数组
const nestedArray = [
  { id: 1, children: [{ id: 2, children: [{ id: 3 }] }] },
  { id: 4, children: [{ id: 5 }] }
];

console.log(buildAncestors(nestedArray));
// 输出: [[1, 2, 3], [1, 2], [1], [4, 5], [4]]

参考链接

JavaScript递归函数示例

常见问题及解决方法

栈溢出：如果嵌套数组非常深，递归方法可能会导致栈溢出。解决方法是使用迭代方法代替递归。

function buildAncestorsIterative(nestedArray) {
  let stack = nestedArray.map(item => ({ item, path: [] }));
  let ancestors = [];

  while (stack.length > 0) {
    let { item, path } = stack.pop();
    let newPath = path.concat(item.id);
    ancestors.push(newPath);
    if (item.children) {
      item.children.forEach(child => {
        stack.push({ item: child, path: newPath });
      });
    }
  }

  return ancestors;
}

性能问题：对于大规模数据，递归和迭代方法都可能性能不佳。可以考虑使用生成器函数来优化性能。

function* buildAncestorsGenerator(nestedArray) {
  function* traverse(arr, currentPath) {
    for (let item of arr) {
      let newPath = currentPath.concat(item.id);
      yield newPath;
      if (item.children) {
        yield* traverse(item.children, newPath);
      }
    }
  }

  yield* traverse(nestedArray, []);
}

const ancestors = [...buildAncestorsGenerator(nestedArray)];
console.log(ancestors);

通过以上方法，可以有效地从嵌套数组构建祖先列表，并解决常见的性能和栈溢出问题。