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.
1var sumOfDistancesInTree = function(n, edges) {
This JavaScript solution uses arrays for graph and state tracking, and recursive functions to propagate results across the tree.
dfs1 traverse computes initial results starting from the root and counts for subtree sizes.dfs2 uses the calculated parent data to update and spread the correct distance sums to each node.