用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; vectorTreeNode* children; }; pairint, int findOptimalLocation(TreeNode* root) { // 第一次DFS计算子树大小和初始距离和 functionvoid(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计算各节点的距离和 functionvoid(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出发找到距离它最远的节点vu和v之间的路径就是树的直径// 两次BFS求直径实现 pairint, int findFarthest(int start, const vectorvectorint adj) { vectorint dist(adj.size(), -1); queueint 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 vectorvectorint edges) { if (edges.empty()) return 0; vectorvectorint 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; }方法时间复杂度空间复杂度适用场景两次DFSO(n)O(n)无权树单次查询树形DPO(n)O(h)带权树需要维护额外信息3. 面试实战LeetCode真题解析3.1 例题一543. 二叉树的直径这道题是树直径的直接应用。关键点在于直径不一定经过根节点因此需要对每个节点都进行考察。class Solution { public: int diameterOfBinaryTree(TreeNode* root) { int res 0; functionint(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: vectorint findMinHeightTrees(int n, vectorvectorint edges) { if (n 1) return {0}; vectorunordered_setint adj(n); for (const auto e : edges) { adj[e[0]].insert(e[1]); adj[e[1]].insert(e[0]); } queueint 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); } } } vectorint res; while (!leaves.empty()) { res.push_back(leaves.front()); leaves.pop(); } return res; } };4. 高级应用与优化技巧4.1 动态树的重心维护在实际应用中树结构可能是动态变化的。这时我们需要高效维护重心位置。一个常用的技巧是利用重心的性质添加/删除叶子节点时重心最多移动一条边。class DynamicCentroid { vectorvectorint adj; vectorint size; vectorbool 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 带权树的重心与直径当树的边或节点有权重时我们需要调整算法。对于带权重心只需将节点计数替换为权重求和对于带权直径则需要在计算路径长度时考虑边权。// 带权直径计算示例 pairint, int weightedDFS(int u, int parent, const vectorvectorpairint, 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 vectorvectorpairint, int adj) { if (adj.empty()) return 0; auto [_, u] weightedDFS(0, -1, adj); auto [diameter, __] weightedDFS(u, -1, adj); return diameter; }在解决实际问题时我发现很多看似复杂的问题都可以转化为树的重心或直径问题。比如社交网络中的信息传播中心选择、物流仓库的最佳选址等。掌握这两个概念能让你在面试中快速识别问题本质给出高效解决方案。 用C++搞定树的重心与直径：从LeetCode到面试题的实战解析（附完整代码）
用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; vectorTreeNode* children; }; pairint, int findOptimalLocation(TreeNode* root) { // 第一次DFS计算子树大小和初始距离和 functionvoid(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计算各节点的距离和 functionvoid(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出发找到距离它最远的节点vu和v之间的路径就是树的直径// 两次BFS求直径实现 pairint, int findFarthest(int start, const vectorvectorint adj) { vectorint dist(adj.size(), -1); queueint 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 vectorvectorint edges) { if (edges.empty()) return 0; vectorvectorint 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; }方法时间复杂度空间复杂度适用场景两次DFSO(n)O(n)无权树单次查询树形DPO(n)O(h)带权树需要维护额外信息3. 面试实战LeetCode真题解析3.1 例题一543. 二叉树的直径这道题是树直径的直接应用。关键点在于直径不一定经过根节点因此需要对每个节点都进行考察。class Solution { public: int diameterOfBinaryTree(TreeNode* root) { int res 0; functionint(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: vectorint findMinHeightTrees(int n, vectorvectorint edges) { if (n 1) return {0}; vectorunordered_setint adj(n); for (const auto e : edges) { adj[e[0]].insert(e[1]); adj[e[1]].insert(e[0]); } queueint 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); } } } vectorint res; while (!leaves.empty()) { res.push_back(leaves.front()); leaves.pop(); } return res; } };4. 高级应用与优化技巧4.1 动态树的重心维护在实际应用中树结构可能是动态变化的。这时我们需要高效维护重心位置。一个常用的技巧是利用重心的性质添加/删除叶子节点时重心最多移动一条边。class DynamicCentroid { vectorvectorint adj; vectorint size; vectorbool 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 带权树的重心与直径当树的边或节点有权重时我们需要调整算法。对于带权重心只需将节点计数替换为权重求和对于带权直径则需要在计算路径长度时考虑边权。// 带权直径计算示例 pairint, int weightedDFS(int u, int parent, const vectorvectorpairint, 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 vectorvectorpairint, int adj) { if (adj.empty()) return 0; auto [_, u] weightedDFS(0, -1, adj); auto [diameter, __] weightedDFS(u, -1, adj); return diameter; }在解决实际问题时我发现很多看似复杂的问题都可以转化为树的重心或直径问题。比如社交网络中的信息传播中心选择、物流仓库的最佳选址等。掌握这两个概念能让你在面试中快速识别问题本质给出高效解决方案。