Sum of Distances in Tree Hard 0 attempts
LeetCode ↗

Sum of Distances in Tree

Hard TreeBinary TreeDFS LeetCode

Given a tree with n nodes, return an array where ans[i] is the sum of distances from node i to all other nodes.

Example: n=6, edges=[[0,1],[0,2],[2,3],[2,4],[2,5]] → [8,12,6,10,10,10]

Sample Input
—
Sample Output
—
Constraints
  • 1 <= n <= 3 * 10^4
  • edges.length == n - 1
Topics
TreeBinary TreeDFS

Two DFS (Re-rooting)

function sumOfDistancesInTree(n, edges) {
  const graph = Array.from({length:n}, ()=>[]);
  for (const [u,v] of edges) { graph[u].push(v); graph[v].push(u); }
  const count = Array(n).fill(1), ans = Array(n).fill(0);
  function dfs1(u, parent) {
    for (const v of graph[u]) if (v!==parent) { dfs1(v, u); count[u]+=count[v]; ans[u]+=ans[v]+count[v]; }
  }
  function dfs2(u, parent) {
    for (const v of graph[u]) if (v!==parent) { ans[v]=ans[u]-count[v]+(n-count[v]); dfs2(v, u); }
  }
  dfs1(0,-1); dfs2(0,-1);
  return ans;
}

Time: O(n) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript