树中距离之和【LC834】
给定一个无向、连通的树。树中有
n个标记为0...n-1的节点以及n-1条边 。给定整数
n和数组edges，edges[i] = [ai, bi]表示树中的节点ai和bi之间有一条边。返回长度为
n的数组answer，其中answer[i]是树中第i个节点与所有其他节点之间的距离之和。
class Solution { private List<Integer>[] g; private int[] ans, size; public int[] sumOfDistancesInTree(int n, int[][] edges) { g = new ArrayList[n]; // g[x] 表示 x 的所有邻居 Arrays.setAll(g, e -> new ArrayList<>()); for (var e : edges) { int x = e[0], y = e[1]; g[x].add(y); g[y].add(x); } ans = new int[n]; size = new int[n]; dfs(0, -1, 0); // 0 没有父节点 reroot(0, -1); // 0 没有父节点 return ans; } private void dfs(int x, int fa, int depth) { ans[0] += depth; // depth 为 0 到 x 的距离 size[x] = 1; for (int y : g[x]) { // 遍历 x 的邻居 y if (y != fa) { // 避免访问父节点 dfs(y, x, depth + 1); // x 是 y 的父节点 size[x] += size[y]; // 累加 x 的儿子 y 的子树大小 } } } private void reroot(int x, int fa) { for (int y : g[x]) { // 遍历 x 的邻居 y if (y != fa) { // 避免访问父节点 ans[y] = ans[x] + g.length - 2 * size[y]; reroot(y, x); // x 是 y 的父节点 } } } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/sum-of-distances-in-tree/solutions/2345592/tu-jie-yi-zhang-tu-miao-dong-huan-gen-dp-6bgb/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
