用C++搞定树的重心与直径：从LeetCode到面试题的实战解析（附完整代码）
树结构作为图论中的经典模型，在算法面试和竞赛中占据着重要地位。无论是Facebook的面试题库还是Google的算法轮考，树的遍历与性质分析都是必考内容。今天我们就来深入探讨两个核心概念——树的重心与直径，它们不仅是理解树结构的关键，更是解决实际问题的利器。
记得去年在准备Google面试时，我遇到一道关于网络节点优化的题目，本质上就是求树的重心。当时因为没有系统掌握这个概念，白白浪费了45分钟。后来系统梳理才发现，这类问题都有固定套路。本文将结合我在LeetCode刷题和实际面试中的经验，带你彻底掌握这两个知识点。
1. 树的重心：概念与算法实现
树的重心（Centroid）是指树中满足特定条件的一个或两个节点。简单来说，删除重心后，剩下的最大子树节点数最小。这个性质在优化问题中非常有用，比如医院选址、网络服务器部署等场景。
1.1 重心的数学定义与性质
重心的正式定义是：对于树中的某个节点，如果删除它后形成的所有子树中，最大子树的节点数最少，那么这个节点就是树的重心。一棵树的重心最多有两个，且如果存在两个重心，它们必定相邻。
重心的几个重要特性：
- 以重心为根的树，所有子树的大小不超过原树的一半
- 树中所有节点到重心的距离之和最小
- 连接两棵树时，新树的重心位于原两树重心的路径上
// 计算树的重心核心代码 void dfs(int u, int parent) { size[u] = 1; // 当前节点本身 int max_subtree = 0; for (int v : adj[u]) { if (v != parent) { dfs(v, u); size[u] += size[v]; max_subtree = max(max_subtree, size[v]); } } max_subtree = max(max_subtree, n - size[u]); if (max_subtree < min_max_size) { centroid = u; min_max_size = max_subtree; } }1.2 实际应用：医院选址问题
LeetCode上有一道经典题目"Minimum Height Trees"，本质上就是找树的重心。来看一个实际案例：
假设我们要在一个社区建立医院，社区道路形成一棵树，每个节点代表一个居民区，人口数不同。目标是选择位置使所有居民到达医院的总距离最小。
struct TreeNode { int population; vector<TreeNode*> children; }; pair<int, int> findOptimalLocation(TreeNode* root) { // 第一次DFS计算子树大小和初始距离和 function<void(TreeNode*, int)> dfs1 = [&](TreeNode* node, int depth) { total_distance += node->population * depth; subtree_size[node] = node->population; for (auto child : node->children) { dfs1(child, depth + 1); subtree_size[node] += subtree_size[child]; } }; // 第二次DFS计算各节点的距离和 function<void(TreeNode*, int)> dfs2 = [&](TreeNode* node, int parent_dist) { current_distance = parent_dist; if (current_distance < min_distance) { min_distance = current_distance; best_location = node; } for (auto child : node->children) { int new_dist = current_distance + (total_population - 2 * subtree_size[child]); dfs2(child, new_dist); } }; // 初始化变量并执行搜索 // ... (完整实现省略) return {best_location->id, min_distance}; }提示：在实际编码中，要注意处理树为空或只有一个节点的边界情况。同时，对于大规模树结构，递归实现可能导致栈溢出，可以考虑迭代方式实现DFS。
2. 树的直径：两种高效解法
树的直径是指树中任意两节点间最长路径的长度。这个概念在网络路由、物流规划等领域有广泛应用。我们来看两种经典解法：两次DFS法和树形DP法。
2.1 两次DFS/BFS算法
这种方法基于一个关键性质：从任意节点出发，距离最远的节点必为直径的一端。算法步骤如下：
- 任选一个起点，找到距离它最远的节点u
- 从u出发，找到距离它最远的节点v
- u和v之间的路径就是树的直径
// 两次BFS求直径实现 pair<int, int> findFarthest(int start, const vector<vector<int>>& adj) { vector<int> dist(adj.size(), -1); queue<int> q; q.push(start); dist[start] = 0; int farthest = start, max_dist = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); if (dist[v] > max_dist) { max_dist = dist[v]; farthest = v; } } } } return {farthest, max_dist}; } int treeDiameter(const vector<vector<int>>& edges) { if (edges.empty()) return 0; vector<vector<int>> adj(edges.size() + 1); for (const auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); } auto [u, _] = findFarthest(0, adj); auto [v, diameter] = findFarthest(u, adj); return diameter; }2.2 树形动态规划解法
对于带权树或需要同时处理多个查询的情况，树形DP是更好的选择。思路是对于每个节点，记录通过它的最长路径（直径候选）。
int diameter = 0; int dfs(TreeNode* root) { if (!root) return 0; int left_depth = dfs(root->left); int right_depth = dfs(root->right); diameter = max(diameter, left_depth + right_depth); return 1 + max(left_depth, right_depth); } int getDiameter(TreeNode* root) { diameter = 0; dfs(root); return diameter; }| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 两次DFS | O(n) | O(n) | 无权树，单次查询 |
| 树形DP | O(n) | O(h) | 带权树，需要维护额外信息 |
3. 面试实战：LeetCode真题解析
3.1 例题一：543. 二叉树的直径
这道题是树直径的直接应用。关键点在于直径不一定经过根节点，因此需要对每个节点都进行考察。
class Solution { public: int diameterOfBinaryTree(TreeNode* root) { int res = 0; function<int(TreeNode*)> dfs = [&](TreeNode* node) { if (!node) return 0; int left = dfs(node->left); int right = dfs(node->right); res = max(res, left + right); return 1 + max(left, right); }; dfs(root); return res; } };注意：在实际面试中，面试官可能会追问如何修改代码来记录直径的具体路径。这时需要额外维护每个节点的父节点信息和最长路径的来源。
3.2 例题二：310. 最小高度树
这道题本质上是寻找树的所有重心。当树有偶数个节点时，可能会有两个重心。
class Solution { public: vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) { if (n == 1) return {0}; vector<unordered_set<int>> adj(n); for (const auto& e : edges) { adj[e[0]].insert(e[1]); adj[e[1]].insert(e[0]); } queue<int> leaves; for (int i = 0; i < n; ++i) { if (adj[i].size() == 1) leaves.push(i); } int remaining = n; while (remaining > 2) { int size = leaves.size(); remaining -= size; for (int i = 0; i < size; ++i) { int leaf = leaves.front(); leaves.pop(); int neighbor = *adj[leaf].begin(); adj[neighbor].erase(leaf); if (adj[neighbor].size() == 1) { leaves.push(neighbor); } } } vector<int> res; while (!leaves.empty()) { res.push_back(leaves.front()); leaves.pop(); } return res; } };4. 高级应用与优化技巧
4.1 动态树的重心维护
在实际应用中，树结构可能是动态变化的。这时我们需要高效维护重心位置。一个常用的技巧是利用重心的性质：添加/删除叶子节点时，重心最多移动一条边。
class DynamicCentroid { vector<vector<int>> adj; vector<int> size; vector<bool> removed; int centroid; void updateSize(int u, int parent) { size[u] = 1; for (int v : adj[u]) { if (v != parent && !removed[v]) { updateSize(v, u); size[u] += size[v]; } } } int findCentroid(int u, int parent, int total) { for (int v : adj[u]) { if (v != parent && !removed[v] && size[v] > total/2) { return findCentroid(v, u, total); } } return u; } public: void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); // 更新重心逻辑 updateCentroid(); } void updateCentroid() { fill(size.begin(), size.end(), 0); updateSize(0, -1); centroid = findCentroid(0, -1, size[0]); } int getCentroid() { return centroid; } };4.2 带权树的重心与直径
当树的边或节点有权重时，我们需要调整算法。对于带权重心，只需将节点计数替换为权重求和；对于带权直径，则需要在计算路径长度时考虑边权。
// 带权直径计算示例 pair<int, int> weightedDFS(int u, int parent, const vector<vector<pair<int, int>>>& adj) { int max_depth = 0, farthest = u; for (auto [v, w] : adj[u]) { if (v != parent) { auto [child_depth, child_node] = weightedDFS(v, u, adj); if (child_depth + w > max_depth) { max_depth = child_depth + w; farthest = child_node; } } } return {max_depth, farthest}; } int findWeightedDiameter(const vector<vector<pair<int, int>>>& adj) { if (adj.empty()) return 0; auto [_, u] = weightedDFS(0, -1, adj); auto [diameter, __] = weightedDFS(u, -1, adj); return diameter; }在解决实际问题时，我发现很多看似复杂的问题都可以转化为树的重心或直径问题。比如社交网络中的信息传播中心选择、物流仓库的最佳选址等。掌握这两个概念，能让你在面试中快速识别问题本质，给出高效解决方案。
