What is the maximum number of minimum height trees a single tree can have?

A tree can have at most two MHT roots, which correspond to the centers of the tree after iterative leaf removal.

Why does the leaf-removal approach guarantee finding all minimum height trees?

Removing leaves layer by layer converges to the central node(s), which by definition minimize height from any chosen root.

Can I use DFS to find minimum height trees?

DFS from each node is possible but inefficient; the BFS leaf-removal approach achieves O(n) time, which is optimal.

How do I handle trees with only one node?

A single-node tree trivially has itself as the only MHT root.

How does indegree and topological ordering apply to this problem?

Indegree counts identify leaves, and topological ordering via BFS ensures iterative pruning correctly identifies tree centers.

#310

Medium

auto_awesome图·搜索

LeetCode 题解工作台

最小高度树

树是一个无向图，其中任何两个顶点只通过一条路径连接。换句话说，任何一个没有简单环路的连通图都是一棵树。给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [a i , b…

深度优先搜索广度优先搜索图拓扑排序

题目描述

树是一个无向图，其中任何两个顶点只通过一条路径连接。换句话说，任何一个没有简单环路的连通图都是一棵树。

给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [a_i, b_i] 表示树中节点 a_i 和 b_i 之间存在一条无向边。

可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。

请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。

树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

示例 1：

输入：n = 4, edges = [[1,0],[1,2],[1,3]]
输出：[1]
解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。

示例 2：

输入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
输出：[3,4]

提示：

1 <= n <= 2 * 10⁴
edges.length == n - 1
0 <= a_i, b_i < n
a_i != b_i
所有 (a_i, b_i) 互不相同
给定的输入保证是一棵树，并且 不会有重复的边

lightbulb

解题思路

方法一：拓扑排序

如果这棵树只有一个节点，那么这个节点就是最小高度树的根节点，直接返回这个节点即可。

如果这棵树有多个节点，那么一定存在叶子节点。叶子节点是只有一个相邻节点的节点。我们可以利用拓扑排序，从外向内剥离叶子节点，当我们到达最后一层的时候，剩下的节点就是最小高度树的根节点。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为节点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]
        g = [[] for _ in range(n)]
        degree = [0] * n
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
            degree[a] += 1
            degree[b] += 1
        q = deque(i for i in range(n) if degree[i] == 1)
        ans = []
        while q:
            ans.clear()
            for _ in range(len(q)):
                a = q.popleft()
                ans.append(a)
                for b in g[a]:
                    degree[b] -= 1
                    if degree[b] == 1:
                        q.append(b)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) since each node and edge is processed once during leaf removal. Space complexity is O(n) for adjacency lists and degree tracking. BFS traversal ensures linear performance for trees of any valid size.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate quickly identifies that leaf nodes can be pruned iteratively to find centers.
question_mark
Candidate uses degree counts and adjacency lists rather than naive height calculations.
question_mark
Candidate correctly returns all remaining nodes as potential MHT roots, handling multiple centers.

warning

常见陷阱

外企场景

error
Failing to account for multiple centers; a tree can have up to two MHT roots.
error
Incorrectly updating degrees or adjacency lists during iterative leaf removal.
error
Attempting DFS from each node, resulting in O(n^2) time instead of O(n) BFS pruning.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Weighted tree where edge lengths vary, requiring recalculation of height based on path sums.
arrow_right_alt
Finding MHT roots in a forest instead of a single connected tree.
arrow_right_alt
Limiting root selection to a subset of nodes rather than all nodes.

help

常见问题

外企场景

继续练习

#329 矩阵中的最长递增路径 #210 课程表 II #207 课程表