找出链条中其对应的所有的父级 name

Question

已知数据格式，实现一个函数 fn ，给一个 id 找出链条中其对应的所有的父级 name，使用 JS 分别用 DFS 和 BFS

数据格式

const data = [
  {
    id: 1,
    name: '中国',
    children: [
      {
        id: 11,
        name: '北京',
        children: [
          {
            id: 111,
            name: '朝阳区',
          },
          {
            id: 112,
            name: '海淀区',
          },
        ],
      },
      {
        id: 12,
        name: '上海',
        children: [
          {
            id: 121,
            name: '浦东新区',
          },
          {
            id: 122,
            name: '徐汇区',
          },
        ],
      },
    ],
  },
  {
    id: 2,
    name: '美国',
    children: [
      {
        id: 21,
        name: '纽约',
        children: [
          {
            id: 211,
            name: '曼哈顿区',
          },
          {
            id: 212,
            name: '布鲁克林区',
          },
        ],
      },
      {
        id: 22,
        name: '洛杉矶',
        children: [
          {
            id: 221,
            name: '好莱坞区',
          },
          {
            id: 222,
            name: '比佛利山庄区',
          },
        ],
      },
    ],
  },
];

DFS

// 使用 DFS 实现
function findParentsDFS(id, data) {
  let result = [];
  function dfs(node, path) {
    if (node.id === id) {
      result = path;
      return;
    }
    if (node.children) {
      for (let i = 0; i < node.children.length; i++) {
        dfs(node.children[i], [...path, node.name]);
      }
    }
  }
  dfs({ children: data }, []);
  return result.slice(1);
}

BFS

// 使用 BFS 实现
function findParentsBFS(id, data) {
  let result = [];
  let queue = [{ node: { children: data }, path: [] }];
  while (queue.length > 0) {
    const { node, path } = queue.shift();
    if (node.id === id) {
      result = path;
      break;
    }
    if (node.children) {
      for (let i = 0; i < node.children.length; i++) {
        queue.push({ node: node.children[i], path: [...path, node.name] });
      }
    }
  }
  return result.slice(1);
}