#yyds干货盘点# 名企真题专题：小米Git

1.简述：

Git 是一个常用的分布式代码管理工具，Git 通过树的形式记录文件的更改历史（例如示例图），树上的每个节点表示一个版本分支，工程师经常需要找到两个分支的最近的分割点。

例如示例图中 3,4 版本的分割点是 1。3,5 版本的分割点是 0。

给定一个用邻接矩阵 matrix 表示的树，请你找到版本 versionA 和 versionB 最近的分割点并返回编号。

注意：

1.矩阵中从第一行 （视为节点 0 ）开始，表示与其他每个点的连接情况，例如 [01011,10100,01000,10000,10000] 表示节点 0 与节点 1 ， 3 ， 4相连，节点 1 与节点 0 ， 2相连，其他点的以此类推。

2.并不保证是一棵二叉树，即一个节点有可能有多个后继节点，我们把节点 0 视为树的根节点。

数据范围：树上节点数量满足 

示例图

输入：

["01011","10100","01000","10000","10000"],1,2

返回值：

1

输入：

["0"],0,0

返回值：

0

2.代码实现：

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;
    }
}