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.*;标签:yyds,Git,真题,int,indexA,father,indexB,depth,节点 From: https://blog.51cto.com/u_15488507/5908655
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;
}
}