最近看到个热议话题：“互联网大厂开始卡32了？” 一时间，网友们炸开了锅，纷纷吐槽。
在外企，甚至35岁以上的程序员依旧是香饽饽。
但32岁之后就开始失去竞争力了吗？说实话，很多时候，外面的机会根本不受年龄限制，反而是更看重你有没有足够的技术深度和经验。
算法题：最小高度树
聊一个有点挑战性的问题：最小高度树（Minimum Height Tree, MHT）。这个问题看似简单，实则可以折磨掉不少程序员，尤其是当我们在面试中遇到它时。为什么？因为它涉及到图论，而且你可能会觉得自己的思路特别“乱”，问题挺多，细节不少，写代码的时候脑袋里各种“坑”都得绕过。
我们知道，树是一个非常经典的数据结构，它由节点和边构成，而且是没有环的。如果你不小心给树加上环，那可就变成了图，麻烦了。最小高度树的题目核心是：给定一个无向图，图的节点数是 (n)，边数是 (m)，要求我们找出所有可能的“最小高度树”。如果你对“高度”理解得不够清晰，我简单解释一下，树的高度是从根节点到最远叶子节点的距离。
首先，最小高度树和普通的树没有本质的区别。它的难点在于，你不仅要建树，还得处理如何选择根节点，使得树的高度最小。基本上就是要找到一个“最佳的根节点”，使得从根节点出发到最远的叶子节点的距离最短。
理解这个问题后，接下来我们就得想办法怎么做了。一个常见的解法就是利用广度优先搜索（BFS）来求解。这听起来可能有点抽象，来，放松一下，我们慢慢梳理。
首先，重点是我们要寻找“树的中心”。你可以把树看成一个人的身体，根节点就是脊椎。而“最小高度树”其实就是要找到树的“脊椎”，确保它的高度最小。树的“中心”是从根节点到所有其他节点的距离最小的节点。简单说，就是：从树的任意节点开始，你做一次广度优先搜索，找出所有节点的距离，选择一个距离最远的节点，然后从这个最远的节点开始再做一次广度优先搜索，再找一个最远的节点。最后，我们就能得到树的中心节点。
简单来讲，BFS的两次过程就是为了找树的“直径”，然后再通过这个直径的中间点，找出最小高度树的根。
接下来，我给大家看个代码示例：
import java.util.*;
public class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) {
return Collections.singletonList(0); // 如果只有一个节点，根节点就是它本身
}
// 构建邻接表
List<Set<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new HashSet<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
// 初始化所有叶子节点
Queue<Integer> leaves = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (graph.get(i).size() == 1) {
leaves.add(i);
}
}
// 剥离叶子节点，直到剩下中心节点
while (n > 2) {
int size = leaves.size();
n -= size; // 每次剥离掉size个叶子节点
for (int i = 0; i < size; i++) {
int leaf = leaves.poll();
// 删除叶子节点
for (int neighbor : graph.get(leaf)) {
graph.get(neighbor).remove(leaf);
if (graph.get(neighbor).size() == 1) {
leaves.add(neighbor); // 新的叶子节点
}
}
}
}
// 剩下的就是最小高度树的根
return new ArrayList<>(leaves);
}
public static void main(String[] args) {
Solution sol = new Solution();
int n = 6;
int[][] edges = {{0, 3}, {1, 3}, {2, 3}, {4, 3}, {5, 4}};
System.out.println(sol.findMinHeightTrees(n, edges)); // 输出：[3, 4]
}
}
在这段代码中，我们首先通过邻接表存储图的结构，然后找出所有的叶子节点（那些只有一个连接的节点）。然后逐步“剥离”这些叶子节点，直到剩下2个节点，这两个节点就是最小高度树的根。简单来说，这个方法就是通过不断剥去外层的叶子，最终找到树的中心。
有时候，这种“剥离叶子”的过程可能让你想起剥洋葱——一层一层地剥，直到你找到那颗最小的核心。这个过程效率很高，时间复杂度为O(N)，因为每个节点和边都只会被访问一次。
总结一下，最小高度树的关键就是找到“树的中心”，这个中心通过两次广度优先搜索可以很高效地找到。大家可以在面试中遇到类似问题时，运用这种思路去解答。
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
