题解 | #小米Git#

function Git( matrix ,  versionA ,  versionB ) {
    const n = matrix.length
//     将string转换为数组更改数组。。。。
    for(let i = 0; i < n; i++) {
        matrix[i] = matrix[i].split('').map(Number)
    }
//     father数组记录当前节点的父元素
    const father = new Array(n).fill(0)
//     level数组记录当前节点的层级，0为0层
    const level = new Array(n).fill(0)

    const q = new Array()
//     BFS遍历每个元素
    q.push(0)
    while (q.length > 0) {
        // 遍历行数
        let index = q.shift()
        for (let i = 1; i < n; i++) {
            if (matrix[index][i] === 1) {
                father[i] = index
                matrix[i][index] = 0
                level[i] = level[index] + 1
                q.push(i)
            }
        }
    }

    while (level[versionA] > level[versionB]) {
        versionA = father[versionA]
    }
    while (level[versionA] < level[versionB]) {
        versionB = father[versionB]
    }
//     如果两个节点位于同一侧
    if (versionA === versionB)
        return versionA
//     如果两个节点位于不同侧
    while (father[versionA] !== father[versionB]) {
        versionA = father[versionA]
        versionB = father[versionB]
    }
    return father[versionA]
}
module.exports = {
    Git : Git
};