【每日一题】- 2020-08-07 - 寻找祖先

[azl397985856]

数据源

let list = [
  {
    id: 1,
    name: "A",
    children: [
      { id: 11, name: "A1" },
      { id: 12, name: "A2" },
      { id: 13, name: "A3" },
    ],
  },
  {
    id: 2,
    name: "B",
    children: [
      { id: 21, name: "B1" },
      { id: 22, name: "B2", children: [{ id: 221, name: "B21" }] },
      { id: 33, name: "B3" },
    ],
  },
];

期望结果 根据已知id221获取其所有祖先节点的id集合

[2, 22]

[suukii]

const findAncestors = (list, target, path = []) => {
    if (!list || list.length === 0) return [];

    for (let item of list) {
        if (item.id === target) return [...path];
        const res = findAncestors(item.children, target, [...path, item.id]);
        if (res.length > 0) return res;
    }
    return [];
};

[azl397985856]

思路

基本的回溯思路，只不过这题值需要求出一个满足条件的解即可，但是我还是套用了多个解的模板。

那你觉得应该如何优化呢？

代码（JS）

function main(id, nodes) {
  ans = [];
  function dfs(node, path) {
    if (node.id === id) return (ans = [...path]);
    path.push(node.id);
    for (const child of node.children || []) dfs(child, path);
    path.pop(node.id);
  }

  for (const node of nodes) {
    dfs(node, []);
    if (ans.length > 0) return ans;
  }
  return [];
}

复杂度分析

• 时间复杂度：$O(N)$，其中 N 为节点总数。
• 空间复杂度：$O(N)$，最坏的情况是一个类链表的结构，我们找到最后一个才找到。

更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode 。 目前已经35K star啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

[hanxuanliang]

const findAncestors = (list, target, path = []) => {
    if (!list || list.length === 0) return [];

    for (let item of list) {
        if (item.id === target) return [...path];
        const res = findAncestors(item.children, target, [...path, item.id]);
        if (res.length > 0) return res;
    }
    return [];
};

参数没懂是什么意思，说明一下？:apple:

[suukii]

@hanxuanliang target 是 已知id221，path 是从根节点到 target 走过的节点id

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.