834. Sum of Distances in Tree
Explanation:
To solve this problem, we can use a depth-first search (DFS) approach. We need to calculate the sum of distances for each node in the tree. The idea is to calculate two values for each node:
count[node]: the number of nodes in the subtree rooted atnode.res[node]: the sum of distances fromnodeto all other nodes.
We start by doing a post-order traversal to calculate count and res for each node. Then, using the values calculated during the post-order traversal, we do a pre-order traversal to update the res values for all nodes by propagating the information from their parent nodes.
:
class Solution {
int[] res, count;
List<Set<Integer>> tree;
public int[] sumOfDistancesInTree(int n, int[][] edges) {
res = new int[n];
count = new int[n];
tree = new ArrayList<>();
for (int i = 0; i < n; i++) {
tree.add(new HashSet<>());
}
for (int[] edge : edges) {
tree.get(edge[0]).add(edge[1]);
tree.get(edge[1]).add(edge[0]);
}
postOrder(0, -1);
preOrder(0, -1);
return res;
}
private void postOrder(int node, int parent) {
for (int child : tree.get(node)) {
if (child == parent) continue;
postOrder(child, node);
count[node] += count[child];
res[node] += res[child] + count[child];
}
count[node]++;
}
private void preOrder(int node, int parent) {
for (int child : tree.get(node)) {
if (child == parent) continue;
res[child] = res[node] - count[child] + count.length - count[child];
preOrder(child, node);
}
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.