题解 | #小米Git#

本质上是一个求最近公共祖先的问题，关键要解决的问题是把输入转换成一个树形结构，这里仍然是用字典来存储：

针对给定的样例["01011","10100","01000","10000","10000"],1,2

以当前节点为key，关联节点为value列表，可以转换为：

{
0:[1,3,4],
1:[0,2],
2:[1],
3:[0],
4:[0]
}

然后使用深度优先递归查找目标节点，把经过的路径以列表记录下来即可。

然后两个节点的路径对比，找到最后的相同元素即为最近的公共祖先。

代码如下：

class Solution:
    def Git(self , matrix: List[str], versionA: int, versionB: int) -> int:
        # write code here
        
        global alist,blist
        alist=[]#用来保存a的路径
        blist=[]#用来保存b的路径
        tree={}
        for i in range(len(matrix)):#整理为字典，树形结构
            tree[i]=[]
            relation=list(matrix[i])
            index=0
            while len(relation)>0:
                r=relation.pop(0)
                if r=="1":
                    tree[i].append(index)
                index+=1
        
        def walk(tmplist,pre,node):
            tmplist.append(node)
            if node ==versionA:#找到a，保存路径
                global alist
                alist=tmplist.copy()
            if node == versionB:#找到b，保存路径，注意这里a和b可能是同一个值，所以不要用else
                global blist
                blist=tmplist.copy()
            for i in tree[node]:#遍历执行下级节点
                if i == pre:#注意跳过来时的节点
                    continue
                walk(tmplist,node,i)
                tmplist.pop()
        walk([],0,0)
        res=0
        while len(alist)>0 and len(blist)>0:#逐个弹出首位比较，直到不相同或者路径为空
            a=alist.pop(0)
            b=blist.pop(0)
            if a==b:
                res=a
            else:
                break
        return res