原生JavaScript如何在嵌套对象中根据id获取父级属性链并拼接为字符串

思路说明 #

通过深度优先遍历（DFS）遍历整个嵌套结构，遍历过程中维护当前节点的路径名称列表，一旦匹配到目标id，直接返回拼接后的路径即可。针对嵌套层级极深的场景，还可以使用迭代版的DFS避免递归调用栈溢出的问题。

1. 递归版实现（嵌套层级不超过1万层的场景可用，写法简洁） #

function getFullPath(tree, targetId) {
  // 递归遍历辅助函数
  const dfs = (node, path) => {
    const currentPath = [...path, node.name];
    // 匹配到目标id直接返回路径
    if (node.id === targetId) {
      return currentPath.join('>');
    }
    // 遍历所有子节点
    for (const child of node.children) {
      const res = dfs(child, currentPath);
      if (res) return res;
    }
    return null;
  }

  // 遍历所有根节点
  for (const rootNode of tree) {
    const result = dfs(rootNode, []);
    if (result) return result;
  }
  return null;
}

// 测试用例
const a = [
  {
    id: 1,
    name: 'NewYork',
    children: [],
  },
  {
    id: 2,
    name: 'Tokyo',
    children: [
      {
        id: 7,
        name: 'Toshima',
        children: [],
      },
      {
        id: 8,
        name: 'Minato',
        children: [
          {
            id: 17,
            name: 'Sugamo',
            children: [],
          },
          {
            id: 18,
            name: 'Kamiichi',
            children: [],
          },
        ],
      },
    ],
  },
];
console.log(getFullPath(a, 18)); // 输出：Tokyo>Minato>Kamiichi

2. 迭代版实现（适配极深嵌套场景，无栈溢出风险） #

如果业务嵌套层级超过JS默认调用栈限制（Chrome环境默认约1万层），可以使用栈模拟递归的迭代版本：

function getFullPathIterative(tree, targetId) {
  // 栈元素结构：[当前节点, 上级路径数组]
  const stack = [];
  // 所有根节点先入栈
  for (const rootNode of tree) {
    stack.push([rootNode, []]);
  }

  while (stack.length > 0) {
    const [currentNode, parentPath] = stack.pop();
    const currentPath = [...parentPath, currentNode.name];
    // 匹配到目标直接返回
    if (currentNode.id === targetId) {
      return currentPath.join('>');
    }
    // 子节点倒序入栈可保证遍历顺序和递归版一致，不需要一致可省略reverse逻辑
    for (let i = currentNode.children.length - 1; i >= 0; i--) {
      stack.push([currentNode.children[i], currentPath]);
    }
  }
  return null;
}

// 测试效果和递归版完全一致
console.log(getFullPathIterative(a, 18)); // 输出：Tokyo>Minato>Kamiichi

额外说明 #

• 如果存在id重复的情况，会返回第一个匹配到的节点路径
• 找不到目标id时会返回null，可根据业务需求调整为返回空字符串等默认值

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