树中距离之和 (opens new window)

• 难度：Hard
• 标签：DFS

刷题思路

• [x] DFS
• [ ] xx

方法 1 DFS

• 思路：
  • 先用数组存储每个节点的子节点数组，方便下钻
  • 计算每个节点包含的节点数 & 与所有子节点的距离和
  • 以父节点建立参考系，计算每个节点到其剩余节点的距离, 公式为:$dist[i]=dist[root]−cnt[i]+(N−cnt[i])$
• 复杂度：
  • 时间 O(n)
  • 空间 O(n)
• 结果：
  • 执行用时：144 ms, 在所有 JavaScript 提交中击败了100.00%的用户
  • 内存消耗：45.4 MB, 在所有 JavaScript 提交中击败了100.00%的用户

var sumOfDistancesInTree = function(N, edges) {
    if (!edges || edges.length===0) return [0]
    const graph = Array.from({ length: N }, () => [])
    edges.forEach(([a, b]) => {
        graph[a].push(b)
        graph[b].push(a)
    })
    const cnt = new Array(N).fill(1) // 节点计数，初始化为 1 即包含自身
    const dist = new Array(N).fill(0) // 距离计数，未开始计算故初始化为 0
    dfs1(graph, cnt, dist, 0, -1)
    dfs2(graph, cnt, dist, 0, -1, N)
    return dist
};

// 计算每个节点的包含的节点数 & 距离
function dfs1(graph, cnt, dist, root, parent) {
    const neighbors = graph[root]
    for (let item of neighbors) {
        if (item === parent) continue
        dfs1(graph, cnt, dist, item, root)
        cnt[root] += cnt[item]
        dist[root] += dist[item] + cnt[item]
    }
}

// 用前序遍历，从上到下，借助根节点计算出当前节点与其他节点的距离差（根节点此时已是计算完毕的）
function dfs2(graph, cnt, dist, root, parent, n) {
    const neighbors = graph[root]
    for (let item of neighbors) {
        if (item === parent) continue
        dist[item] = dist[root] - cnt[item] + n - cnt[item]
        dfs2(graph, cnt, dist, item, root, n)
    }
}

方法 2

• 复杂度：
  • 时间 O()
  • 空间 O()

JS刷题记录 Leetcode-js (opens new window) 每周都会更新刷题心得或者题解, 你的点赞或 star 都将助力我产出更好内容~