题解 | #小米Git#

# -*- coding:utf-8 -*-
from typing import List
class Solution:
    global List
    def Git(self, matrix: List[str], versionA: int, versionB: int) -> int:
        # write code here
        # 首先将每个节点的邻接节点识别出来
        neigh_set = dict()
        for i in range(len(matrix)):
            neigh_set[i] = self.get_neighbor(matrix[i])
        self.search(neigh_set, versionA, 0, 0, [])
        a_path = a_list
        self.search(neigh_set, versionB, 0, 0, [])
        b_path = a_list

        for i in range(min(len(a_path), len(b_path))):
            if a_path[i] != b_path[i]:
                return a_path[i - 1]
                break
            else:
                if i == min(len(a_path), len(b_path)) - 1:
                    return a_path[i]

    # 识别相连节点
    def get_neighbor(self, char: str) -> list:
        neighbor = []
        for i in range(len(char)):
            if char[i] == "1":
                neighbor.append(i)
        return neighbor

    # 从根节点开始搜索给定的节点，深度优先
    # 为了防止重复搜索： 1）构建邻接节点字典时只考虑子节点，不考虑父节点
    #                   2）搜索时记录下之前的节点，例如从1-2时，2-1时跳过

    def search(
        self, adj: dict, tar: int, pre_node: int, current_node: int, path: list
    ) -> list:

        """
        adj:{0:[1,2,3],
             1:[0],
             ...
            }
        """
        global flag
        flag = 0
        if current_node == tar:
            path.append(current_node)
            global a_list
            a_list = path.copy()
            flag = 1
        else:

            for node in adj[current_node]:
                if node != pre_node:
                    path.append(current_node)
                    self.search(adj, tar, current_node, node, path)
                    path.pop()
                    if flag:
                        break