题解 | #小米Git#

import java.util.*;


public class Solution {
    
    public void dfs(int node, int father, int dep, int[] path, int[] depth,String[] mat) {
        depth[node] = dep;
        path[node] = father;
        for (int i = 0; i < mat.length; i++) {
            if (i != father && mat[node].charAt(i)=='1') {
                dfs(i,node,dep+1,path,depth,mat);
            }
        }
    }
    public int Git(String[] matrix, int indexA, int indexB) {
        int n  = matrix.length;
        int[] depth = new int[n];
        int[] father = new int[n];
        father[0] = -1;
        dfs(0,-1,0,father,depth,matrix);
        while (depth[indexA] > depth[indexB]) {
            indexA = father[indexA];
        }
        while (depth[indexB] > depth[indexA]) {
            indexB = father[indexB];
        }
        while (indexA != indexB) {
            indexA = father[indexA];
            indexB = father[indexB];
        }
        return indexA;
    }
}