↓Skip to main content
  1. Posts/

LeetCode-310 最小高度树

·1 min·
Table of Contents

LeetCode-310 最小高度树 #

Solution 1 #

寻找最小高度树, 等价于寻找距离最大的两个节点. 有一种寻找方式是从任意一个节点出发, 找到最远的点 $x$ ; 再从 $x$ 出发, 找到最远的点 $y$ , 这里的 $x, y$ 就是相距最远的两个点.

涉及到的详细的证明可以参考: 力扣官方题解.

代码如下:

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]

        g = [[] for _ in range(n)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
        parents = [0] * n
        maxDepth, node = 0, -1

        def dfs(x: int, pa: int, depth: int):
            nonlocal maxDepth, node
            if depth > maxDepth:
                maxDepth, node = depth, x
            parents[x] = pa
            for y in g[x]:
                if y != pa:
                    dfs(y, x, depth + 1)
        dfs(0, -1, 1)
        maxDepth = 0
        dfs(node, -1, 1)

        path = []
        while node != -1:
            path.append(node)
            node = parents[node]
        m = len(path)
        return [path[m // 2]] if m % 2 else [path[m // 2 - 1], path[m // 2]]