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.
1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7 vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
8 vector<int> res(n, 0);
9 vector<int> count(n, 1);
10 unordered_map<int, vector<int>> graph;
11 for (auto &e : edges) {
12 graph[e[0]].push_back(e[1]);
13 graph[e[1]].push_back(e[0]);
14 }
15
16 function<void(int, int)> dfs1 = [&](int node, int parent) {
17 for (int nei : graph[node]) {
18 if (nei == parent) continue;
19 dfs1(nei, node);
20 count[node] += count[nei];
21 res[node] += res[nei] + count[nei];
22 }
23 };
24
25 function<void(int, int)> dfs2 = [&](int node, int parent) {
26 for (int nei : graph[node]) {
27 if (nei == parent) continue;
28 res[nei] = res[node] - count[nei] + (n - count[nei]);
29 dfs2(nei, node);
30 }
31 };
32
33 dfs1(0, -1);
34 dfs2(0, -1);
35 return res;
36 }
37};This C++ solution also implements two DFS traversals with lambda functions:
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.