834. Sum of Distances in Tree
Approach
Two DFS passes; first computes subtree sizes and sum of distances from root, second reroots to derive answers for all nodes.
Key Techniques
Tree problems typically require recursive DFS or iterative BFS. Common patterns: preorder for serialization, inorder for BST sorted output, postorder for bottom-up aggregation. Always consider edge cases: null nodes, single-node trees, and skewed (list-like) trees.
DFS explores as far as possible before backtracking. Use it for path finding, cycle detection, connected components, and tree traversal. Implement recursively (implicit call stack) or iteratively with an explicit Stack<T>. Mark visited nodes to avoid infinite loops in graphs.
Graph algorithms model relationships between entities. Core algorithms: DFS/BFS for traversal, Dijkstra for weighted shortest path, Bellman-Ford for negative weights, Floyd-Warshall for all-pairs, and Kruskal/Prim for minimum spanning trees. Represent graphs as adjacency lists (Dictionary<int, List<int>>) for efficiency.
// Approach: Two DFS passes; first computes subtree sizes and sum of distances from root, second reroots to derive answers for all nodes.
// Time: O(n) Space: O(n)
public class Solution
{
public int[] SumOfDistancesInTree(int n, int[][] edges)
{
var ans = new int[n];
var adjList = new List<List<int>>();
var count = new int[n];
Array.Fill(count, 1);
for (int i = 0; i < n; i++)
adjList.Add(new List<int>());
foreach (int[] edge in edges)
{
int u = edge[0];
int v = edge[1];
adjList[u].Add(v);
adjList[v].Add(u);
}
DFS(0, -1, adjList, count, ans);
DFS2(0, -1, adjList, ans, count, n);
return ans;
}
private void DFS(int node, int parent, List<List<int>> adjList, int[] count, int[] ans)
{
foreach (int child in adjList[node])
{
if (child != parent)
{
DFS(child, node, adjList, count, ans);
count[node] += count[child];
ans[node] += ans[child] + count[child];
}
}
}
private void DFS2(int node, int parent, List<List<int>> adjList, int[] ans, int[] count, int n)
{
foreach (int child in adjList[node])
{
if (child != parent)
{
ans[child] = ans[node] - count[child] + (n - count[child]);
DFS2(child, node, adjList, ans, count, n);
}
}
}
}