【每日一题】- 2020-08-07 - 寻找祖先 about fe-interview HOT 5 CLOSED

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 [];
};

from fe-interview.

思路

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

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

代码（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啦。

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

from fe-interview.

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:

from fe-interview.

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

from fe-interview.

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.

from fe-interview.