# 834. Sum of Distances in Tree

An undirected, connected tree with `N` nodes labelled `0...N-1` and `N-1` `edges` are given.

The `i`th edge connects nodes `edges[i][0] `and` edges[i][1]` together.

Return a list `ans`, where `ans[i]` is the sum of the distances between node `i` 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:
Here is a diagram of the given tree:
0
/ \
1   2
/|\
3 4 5
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.
``````

``````  0
/
1
``````

``````  0
/ \
1   2
``````

``````    0
/ \
1   2
/ \
3   4
``````

``````count[root] = sum(count[i]) + 1
res[root] = sum(res[i]) + sum(count[i])
``````

``````res[i] = res[root] - count[i] + N - count[i]
``````

``````class Solution {
public:
vector<int> sumOfDistancesInTree(int N, vector<vector<int>>& edges) {
vector<int> res(N), count(N);
vector<vector<int>> tree(N);
for (auto &edge : edges) {
tree[edge[0]].push_back(edge[1]);
tree[edge[1]].push_back(edge[0]);
}
helper(tree, 0, -1, count, res);
helper2(tree, 0, -1, count, res);
return res;
}
void helper(vector<vector<int>>& tree, int cur, int pre, vector<int>& count, vector<int>& res) {
for (int i : tree[cur]) {
if (i == pre) continue;
helper(tree, i, cur, count, res);
count[cur] += count[i];
res[cur] += res[i] + count[i];
}
++count[cur];
}
void helper2(vector<vector<int>>& tree, int cur, int pre, vector<int>& count, vector<int>& res) {
for (int i : tree[cur]) {
if (i == pre) continue;
res[i] = res[cur] - count[i] + count.size() - count[i];
helper2(tree, i, cur, count, res);
}
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/834

Binary Tree Postorder Traversal

Binary Tree Preorder Traversal

Distribute Coins in Binary Tree

https://leetcode.com/problems/sum-of-distances-in-tree/

https://leetcode.com/problems/sum-of-distances-in-tree/discuss/161975/My-DFS-sulotion-two-passes

https://leetcode.com/problems/sum-of-distances-in-tree/discuss/130583/C%2B%2BJavaPython-Pre-order-and-Post-order-DFS-O(N)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation