【字节前端面试算法题】路径查找

算法题

实现一个函数，参数为数组和 id，要求实现一个 findPath 方法，找出查找匹配对应 id 的路径。

function findPath(data, id) {
  // ...
}

测试用例

id 全局唯一无序
id = "1" => ["1"]
id = "9" => ["7", "8", "9"]
id = "100"=> []

测试数据如下：

const data = [
  {
    id: "1",
    sub: [
      {
        id: "2",
        sub: [
          {
            id: "3",
            sub: null,
          },
          {
            id: "4",
            sub: [
              {
                id: "6",
                sub: null,
              },
            ],
          },
          {
            id: "5",
            sub: null,
          },
        ],
      },
    ],
  },
  {
    id: "7",
    sub: [
      {
        id: "8",
        sub: [
          {
            id: "9",
            sub: null,
          },
        ],
      },
    ],
  },
  {
    id: "10",
    sub: null,
  },
];

实现思路

路径查找相关的问题，可以使用回溯算法即可

function findPath(data, id) {
  let ret = [];
  /**
   * @param {*} arr   arr 存储当前的临时数组
   * @param {*} child child 遍历数组
   * @returns
   */
  const dfs = (arr, child = []) => {
    if (arr[arr.length - 1] == id) {
      ret = arr.slice();
      return;
    }
    for (let i = 0; i < (child || []).length; i++) {
      const id = child[i].id;
      arr.push(id);
      dfs(arr, child[i].sub);
      arr.pop();
    }
  };
  dfs([], data);
  return ret;
}

console.log(findPath(data, "1")); // ['1']
console.log(findPath(data, "9")); // ['7', '8', '9']
console.log(findPath(data, "100")); // []