面试题库 › Java 后端 › 最小高度树(LC310)

最小高度树(LC310)

难度 ★★☆在 1 场真实面经中被问到 方向:Java 后端考点:图论

哪些公司问过

美团1

常见岗位:Java 后端

答案要点

  1. 最小高度树的根是树的中心,最多两个,即直径中点
  2. 拓扑剥离:度为 1 的叶子逐层删除,剩 1 到 2 个节点为答案
  3. 删除叶子时邻居度数减一,变为 1 则加入下一层
  4. 两次 BFS 求直径,取中点也可
  5. 时间空间 O(n),n 为 1 时返回 [0]

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题