如何将parent-relation数组转换为根到叶路径形式的二维数组

实现思路 #

• 第一步：构建节点ID映射表，可实现O(1)时间通过ID查找对应节点，同时提前记录每个节点的子节点列表，降低后续遍历的时间复杂度
• 第二步：筛选所有根节点（parentId为null的节点）作为所有路径的起点
• 第三步：通过深度优先遍历每个根节点的子树，每访问一个节点就将其加入当前路径，当遍历到没有子节点的叶子节点时，将当前路径的副本存入结果数组
• 小数据量场景也可使用反向逻辑：遍历所有节点作为叶子节点，依次向上查找父节点直到根节点，反转路径后存入结果，无需提前构建子节点映射

代码实现 #

function convertToPathArray(arr) {
  // 构建id到节点的映射，同时存储每个节点的子节点列表
  const nodeMap = new Map();
  const childrenMap = new Map();
  arr.forEach(node => {
    nodeMap.set(node.id, node);
    if (!childrenMap.has(node.parentId)) {
      childrenMap.set(node.parentId, []);
    }
    childrenMap.get(node.parentId).push(node);
  });

  const result = [];

  // 深度优先遍历拼接路径
  const dfs = (currentId, currentPath) => {
    const currentNode = nodeMap.get(currentId);
    const newPath = [...currentPath, currentNode];
    const children = childrenMap.get(currentId) || [];
    // 没有子节点说明是叶子节点，路径完成存入结果
    if (children.length === 0) {
      result.push(newPath);
      return;
    }
    // 遍历所有子节点继续拼接路径
    children.forEach(child => {
      dfs(child.id, newPath);
    });
  };

  // 从所有根节点开始遍历
  const rootNodes = arr.filter(node => node.parentId === null);
  rootNodes.forEach(root => {
    dfs(root.id, []);
  });

  return result;
}

测试示例 #

// 测试用例1：用户提供的输入
const array = [{id: 1, parentId: 2}, {parentId: null, id: 2}];
console.log(convertToPathArray(array));
// 输出：[ [ { parentId: null, id: 2 }, { id: 1, parentId: 2 } ] ]

// 测试用例2：多层级多分支场景
const array2 = [
  {id: 1, parentId: null},
  {id: 2, parentId: 1},
  {id: 3, parentId: 2},
  {id: 4, parentId: 1},
  {id: 5, parentId: null}
];
console.log(convertToPathArray(array2));
/* 输出：
[
  [ {id:1, parentId:null}, {id:2, parentId:1}, {id:3, parentId:2} ],
  [ {id:1, parentId:null}, {id:4, parentId:1} ],
  [ {id:5, parentId:null} ]
]
*/

注意事项 #

如果业务数据存在循环引用的可能，需要在DFS逻辑中增加已访问节点的判断，避免出现死循环。

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