LeetCode 最小高度树题解

LeetCode 最小高度树题解题目描述给定一个无环图找到最小高度树的根节点。示例输入n 4,edges [[1,0],[1,2],[1,3]]输出[1]解题思路方法拓扑排序思路使用拓扑排序删除所有叶子节点。重复删除直到剩余节点数小于等于 2。剩余的节点就是最小高度树的根节点。复杂度分析时间复杂度O(V E)。空间复杂度O(V E)。代码实现from collections import deque def find_min_height_trees(n, edges): if n 1: return [0] graph [[] for _ in range(n)] indegree [0] * n for u, v in edges: graph[u].append(v) graph[v].append(u) indegree[u] 1 indegree[v] 1 leaves deque([i for i in range(n) if indegree[i] 1]) remaining n while remaining 2: size len(leaves) remaining - size for _ in range(size): leaf leaves.popleft() for neighbor in graph[leaf]: indegree[neighbor] - 1 if indegree[neighbor] 1: leaves.append(neighbor) return list(leaves) # 测试 def test_find_min_height_trees(): n 4 edges [[1, 0], [1, 2], [1, 3]] print(find_min_height_trees(n, edges)) # 输出[1] if __name__ __main__: test_find_min_height_trees()总结最小高度树是拓扑排序的典型应用通过删除叶子节点来找出最小高度树的根节点。