Hard

题目描述

有一个无向连通树，包含 n 个节点，节点标号从 0 到 n - 1，以及 n - 1 条边。

给你整数 n 和数组 edges，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。

返回长度为 n 的数组 answer，其中 answer[i] 是树中第 i 个节点与所有其他节点之间的距离之和。

示例 1：

输入：n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
输出：[8,12,6,10,10,10]
解释：树如上图所示。
我们可以看到 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) 
等于 1 + 1 + 2 + 2 + 2 = 8。
因此，answer[0] = 8，以此类推。

示例 2：

输入：n = 1, edges = []
输出：[0]

示例 3：

输入：n = 2, edges = [[1,0]]
输出：[1,1]

提示：

  • 1 <= n <= 3 * 10^4
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • 给定输入表示一棵有效的树

解题思路

这是一道经典的树形DP问题，需要计算每个节点到所有其他节点的距离之和。如果直接对每个节点进行DFS计算距离，时间复杂度会达到O(n²)，对于n=3×10⁴的数据规模会超时。

最优解法：换根DP（树形DP）

核心思想是通过两次DFS来解决：

  1. 第一次DFS：以任意节点（通常选择0）为根，计算每个子树的节点数量和根节点到所有节点的距离之和

    • count[i]：以i为根的子树中的节点数量
    • dist[0]：节点0到所有其他节点的距离之和

  2. 第二次DFS：利用换根技巧，从已知的根节点答案推导出其他节点的答案

    • 当从父节点转移到子节点时，距离发生变化：
      • 子树内的节点距离减少1
      • 子树外的节点距离增加1
    • 状态转移：answer[child] = answer[parent] - count[child] + (n - count[child])

这种方法的精髓在于避免重复计算，通过一次预处理和一次换根遍历就能得到所有节点的答案，时间复杂度降为O(n)。

代码实现

class Solution {
public:
    vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph(n);
        vector<int> count(n, 1);
        vector<int> answer(n, 0);
        
        // 构建邻接表
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        // 第一次DFS：计算子树节点数和根节点0的距离之和
        function<void(int, int)> dfs1 = [&](int node, int parent) {
            for (int child : graph[node]) {
                if (child != parent) {
                    dfs1(child, node);
                    count[node] += count[child];
                    answer[node] += answer[child] + count[child];
                }
            }
        };
        
        // 第二次DFS：换根DP，计算所有节点的答案
        function<void(int, int)> dfs2 = [&](int node, int parent) {
            for (int child : graph[node]) {
                if (child != parent) {
                    answer[child] = answer[node] - count[child] + (n - count[child]);
                    dfs2(child, node);
                }
            }
        };
        
        dfs1(0, -1);
        dfs2(0, -1);
        
        return answer;
    }
};

class Solution:
    def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
        from collections import defaultdict
        
        graph = defaultdict(list)
        count = [1] * n
        answer = [0] * n
        
        # 构建邻接表
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        # 第一次DFS：计算子树节点数和根节点0的距离之和
        def dfs1(node, parent):
            for child in graph[node]:
                if child != parent:
                    dfs1(child, node)
                    count[node] += count[child]
                    answer[node] += answer[child] + count[child]
        
        # 第二次DFS：换根DP，计算所有节点的答案
        def dfs2(node, parent):
            for child in graph[node]:
                if child != parent:
                    answer[child] = answer[node] - count[child] + (n - count[child])
                    dfs2(child, node)
        
        dfs1(0, -1)
        dfs2(0, -1)
        
        return answer

public class Solution {
    public int[] SumOfDistancesInTree(int n, int[][] edges) {
        List<int>[] graph = new List<int>[n];
        int[] count = new int[n];
        int[] answer = new int[n];
        
        // 初始化
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
            count[i] = 1;
        }
        
        // 构建邻接表
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        
        // 第一次DFS：计算子树节点数和根节点0的距离之和
        void Dfs1(int node, int parent) {
            foreach (int child in graph[node]) {
                if (child != parent) {
                    Dfs1(child, node);
                    count[node] += count[child];
                    answer[node] += answer[child] + count[child];
                }
            }
        }
        
        // 第二次DFS：换根DP，计算所有节点的答案
        void Dfs2(int node, int parent) {
            foreach (int child in graph[node]) {
                if (child != parent) {
                    answer[child] = answer[node] - count[child] + (n - count[child]);
                    Dfs2(child, node);
                }
            }
        }
        
        Dfs1(0, -1);
        Dfs2(0, -1);
        
        return answer;
    }
}

var sumOfDistancesInTree = function(n, edges) {
    const graph = Array(n).fill(null).map(() => []);
    const count = Array(n).fill(1);
    const answer = Array(n).fill(0);
    
    // 构建邻接表
    for (const [a, b] of edges) {
        graph[a].push(b);
        graph[b].push(a);
    }
    
    // 第一次DFS：计算子树节点数和根节点0的距离之和
    const dfs1 = (node, parent) => {
        for (const child of graph[node]) {
            if (child !== parent) {
                dfs1(child, node);
                count[node] += count[child];
                answer[node] += answer[child] + count[child];
            }
        }
    };
    
    // 第二次DFS：换根DP，计算所有节点的答案
    const dfs2 = (node, parent) => {
        for (const child of graph[node]) {
            if (child !== parent) {
                answer[child] = answer[node] - count[child] + (n - count[child]);
                dfs2(child, node);
            }
        }
    };
    
    dfs1(0, -1);
    dfs2(0, -1);
    
    return answer;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要进行两次DFS遍历，每次遍历访问所有节点一次
空间复杂度O(n)需要存储邻接表、count数组、answer数组和递归调用栈

相关题目