树的“最优中心”怎么找？别再暴力试了，Minimum Height Trees 一招搞定

树的“最优中心”怎么找？别再暴力试了，Minimum Height Trees 一招搞定

一、引子：你是不是也写过这种“暴力解法”？

说个很真实的场景。

面试官给你一道题：
👉 给你一棵树，找出所有“最小高度树”的根节点。

你第一反应可能是：

“那我每个点都当根，跑一遍 BFS，算高度，选最小的！”

听起来很合理，对吧？

但我可以直接告诉你：

👉这种解法，90%的人写过，90%的人也被它拖死过。

为什么？

• n 个节点
• 每个节点 BFS 一次
• 时间复杂度：O(n²)

👉 一旦 n 上万，直接凉凉。

二、问题本质：你到底在找什么？

先别急着优化，我们先把问题讲透。

什么是“最小高度树”？

给定一个无向树（无环连通图），选择一个节点作为根，使得：

👉树的高度最小

举个例子：

1