最小高度树(LC310)
哪些公司问过
答案要点
- 最小高度树的根是树的中心,最多两个,即直径中点
- 拓扑剥离:度为 1 的叶子逐层删除,剩 1 到 2 个节点为答案
- 删除叶子时邻居度数减一,变为 1 则加入下一层
- 两次 BFS 求直径,取中点也可
- 时间空间 O(n),n 为 1 时返回 [0]
易错点
- 循环条件写成剩下 1 个节点才停,漏掉两个中心的情况
- n 等于 1 时没有特殊处理
- 按拓扑排序思路处理但用了有向图的入度
面试官常见追问
- 为什么答案最多两个?
- 暴力做法有什么问题?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。