Sponsored
Sponsored
This approach involves two main DFS passes to calculate the sum of distances using subtree properties.
Time Complexity: O(n), Space Complexity: O(n), due to the graph representation and DFS recursion stack.
1from collections import defaultdict
2
3class Solution:
4 def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
5 graph = defaultdict(list)
6 for u, v in edges:
7 graph[u].append(v)
8 graph[v].append(u)
9
10 res = [0] * n
11 count = [1] * n
12
13 def dfs1(node: int, parent: int):
14 for nei in graph[node]:
15 if nei == parent:
16 continue
17 dfs1(nei, node)
18 count[node] += count[nei]
19 res[node] += res[nei] + count[nei]
20
21 def dfs2(node: int, parent: int):
22 for nei in graph[node]:
23 if nei == parent:
24 continue
25 res[nei] = res[node] - count[nei] + (n - count[nei])
26 dfs2(nei, node)
27
28 dfs1(0, -1)
29 dfs2(0, -1)
30
31 return resHere, we use two DFS functions:
dfs1 computes the initial result for the root and counts the number of nodes in each subtree.dfs2 recalculates the result for each node by reusing and adjusting the results from its parent, leveraging the relationship: res[child] = res[parent] - count[child] + (n - count[child]).This approach uses dynamic programming principles and recursive relationships between nodes to determine distances, updating accumulated state data as we compute each node's distance sum.
Time Complexity: O(n), Space Complexity: O(n), resulting from recursive DFS and storage of results and counts for each node.
1import java.util.ArrayList;
2import
In Java, this implementation involves running two recursive functions:
dfs1 aggregates initial path sums and node counts.dfs2 dynamically redistributes total distances by applying the recursive relationship using parent data.