这个题目的意思其实就是要分别从根节点开始遍历(dfs)到给定的两个点，然后从得出的路径中获取最早相同的点即为结果。
class Solution {
public:
/**
* 返回git树上两点的最近分割点
*
* @param matrix 接邻矩阵，表示git树，matrix[i][j] == '1' 当且仅当git树中第i个和第j个节点有连接，节点0为git树的跟节点
* @param indexA 节点A的index
* @param indexB 节点B的index
* @return 整型
*/
int getSplitNode(vector<string> matrix, int indexA, int indexB) {
if(indexA == indexB) return indexA;
int len = matrix.size();
vector<int> vis1(len , 0);
vector<int> vis2(len , 0);
vector<int> rds1;
vector<int> rds2;
rds1.push_back(0);
rds2.push_back(0);
vis1[0] = 1;
vis2[0] = 1;
getRoadList(matrix,0,indexA,vis1,rds1);
getRoadList(matrix,0,indexB, vis2,rds2);
int ans = 0 , j = rds1.size() -1 ;
for( ; j > 0 ; j --)
for( int i = rds2.size() -1 ; i > 0 ; i --){
if(rds1[j] == rds2[i])
return rds1[j];
}
return ans;
}
bool getRoadList(vector<string> matrix , int start , int index , vector<int>& vis, vector<int>& rds){
string str = matrix[start];
for(int i = 0 ; i < str.length() ; i ++){
if(vis[i]) continue;
if(str[i] == '1' ){
vis[i] = 1;
if(i == index){
rds.push_back(index);
return true;
}
else{
rds.push_back(i);
if(!getRoadList(matrix , i , index , vis , rds)){
rds.pop_back();
vis[i] = 0;
}else{
return true;
}
}
}
}
return false;
}
};