已知子文件夹，如何从文件夹数组中找到对应的根文件夹？

问题描述 #

已知包含所有文件夹的数组allFolders，以及其中一个子文件夹selectedFolder，需要获取该子文件夹所属的根文件夹（根文件夹的parent_id为null）。

现有代码问题 #

你当前的尝试代码逻辑方向有误，它在遍历文件夹的子节点寻找匹配项，没有实现向上追溯父节点直到根的逻辑，因此无法得到目标根文件夹。

解决方案 #

我们可以先将所有文件夹（包括嵌套的子文件夹）整理成一个以id为键的映射表，实现快速查找父节点，再从selectedFolder开始向上追溯，直到找到parent_id为null的根文件夹。

完整代码实现 #

const selectedFolder = {id: 6, parent_id: 5, children: []};

const allFolders = [
  {
    id: 1, // ROOT
    parent_id: null,
    children: [
      {
        id: 2,
        parent_id: 1,
        children: [{ id: 3, parent_id: 2, children: [] }],
      },
    ],
  },
  {
    id: 4, // ROOT
    parent_id: null,
    children: [
      {
        id: 5,
        parent_id: 4,
        children: [{ id: 6, parent_id: 5, children: [] }],
      },
    ],
  },
];

// 构建文件夹ID到对象的映射表
function buildFolderMap(folders) {
  const folderMap = new Map();
  // 递归遍历所有文件夹，存入映射表
  function traverse(folder) {
    folderMap.set(folder.id, folder);
    folder.children.forEach(traverse);
  }
  folders.forEach(traverse);
  return folderMap;
}

// 查找选中文件夹对应的根文件夹
function findRootFolder(selected, folders) {
  const folderMap = buildFolderMap(folders);
  let current = selected;
  // 向上追溯直到找到parent_id为null的根
  while (current.parent_id !== null) {
    current = folderMap.get(current.parent_id);
    // 处理数据异常情况（比如找不到父节点）
    if (!current) break;
  }
  return current;
}

// 测试调用
const targetRoot = findRootFolder(selectedFolder, allFolders);
console.log(targetRoot); // 输出：{id: 4, parent_id: null, children: [...]}

代码说明 #

1. buildFolderMap函数：递归遍历所有文件夹（包括嵌套子文件夹），将每个文件夹的id作为键、文件夹对象作为值存入Map，实现O(1)时间复杂度的快速查找。
2. findRootFolder函数：从选中的文件夹开始，不断通过映射表查找其父节点，直到找到parent_id为null的根文件夹。同时加入了异常处理，避免因数据错误导致的崩溃。

另一种递归实现（可选） #

如果你偏好递归方式，也可以用递归遍历整个文件夹树，判断当前树是否包含选中的文件夹，找到则返回根节点：

function findRootRecursive(selected, folders) {
  for (const folder of folders) {
    // 判断当前文件夹或其子文件夹是否包含选中的文件夹
    function containsTarget(node) {
      if (node.id === selected.id) return true;
      return node.children.some(containsTarget);
    }
    if (containsTarget(folder)) {
      return folder;
    }
  }
  return null;
}

// 测试调用
const recursiveRoot = findRootRecursive(selectedFolder, allFolders);
console.log(recursiveRoot); // 输出目标根文件夹

这种方式适合文件夹嵌套深度不大的场景，若嵌套过深可能存在栈溢出风险，此时推荐使用第一种映射表的方式。

内容的提问来源于stack exchange，提问作者Alex Nilson