There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.
You are given the integer n and the array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
Return an array answer of length n where answer[i] is the sum of the distances between the ith node in the tree and all other nodes.
Example 1:
Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]] Output: [8,12,6,10,10,10] Explanation: The tree is shown above. We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) equals 1 + 1 + 2 + 2 + 2 = 8. Hence, answer[0] = 8, and so on.
Example 2:
Input: n = 1, edges = [] Output: [0]
Example 3:
Input: n = 2, edges = [[1,0]] Output: [1,1]
Constraints:
1 <= n <= 3 * 104edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biThis approach involves two main DFS passes to calculate the sum of distances using subtree properties.
Here, 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]).C++
Time Complexity: O(n), Space Complexity: O(n), due to the graph representation and DFS recursion stack.
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.
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.JavaScript
Time Complexity: O(n), Space Complexity: O(n), resulting from recursive DFS and storage of results and counts for each node.
| Approach | Complexity |
|---|---|
| DFS with Two Passes | Time Complexity: O(n), Space Complexity: O(n), due to the graph representation and DFS recursion stack. |
| Dynamic Programming and Recursion | Time Complexity: O(n), Space Complexity: O(n), resulting from recursive DFS and storage of results and counts for each node. |
Sum of Distances in Tree | Google | Leetcode 834 | codestorywithMIK • codestorywithMIK • 17,694 views views
Watch 9 more video solutions →Practice Sum of Distances in Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor