题解 | #小米Git#

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) {
        vector<bool>state1(matrix.size(),false);
        vector<bool>state2(matrix.size(),false);
        vector<int>path1;
        vector<int>path2;
        bool findA=findpath(matrix,0,indexA,path1,state1);
        bool findB=findpath(matrix,0,indexB,path2,state2);
        int res=path1[0];
        for(int i=1;i<path1.size()&&i<path2.size();i++){
            if(path1[i]==path2[i])
                res=path1[i];
            else{
                break;
            }
        }
        return res;
    }
    
    
private:
    
    bool findpath(vector<string> &matrix,int root,int index,vector<int>&path,vector<bool>&state){
        path.push_back(root);
        state[root]=true;
        if(index==root)
            return true;
        bool isfind=false;
        for(int i=0;i<matrix[root].size();i++){
            if(matrix[root][i]=='1'&&state[i]==false&&!isfind){
                isfind=findpath(matrix, i,index, path, state);
                if(isfind)
                   break;
                else{
                    path.pop_back();
                }
            }
        }
        return isfind;
    }
};