题解 | 小米Git

class Solution:
    def Git(self , matrix: List[str], versionA: int, versionB: int) -> int:
        n = len(matrix)
        g = [[] for _ in range(n)]
        for i,c in enumerate(matrix):
            for j,x in enumerate(c):
                if x=='1':
                    g[i].append(j)
        print(g)
        parent = {}
        def dfs(node,par):
            for ner in g[node]:
                if ner!=par:
                    parent[ner] = node
                    dfs(ner, node)
        dfs(0,-1)
        parent[0] = -1
        print(parent)
        pathA = set()
        while versionA!=-1:
            pathA.add(versionA)
            versionA = parent[versionA]
        while versionB not in pathA:
            versionB = parent[versionB]
        return versionB

可以使用深度优先搜索（DFS）来记录每个节点到根节点的路径，然后找到这两个路径的最近公共祖先。