题解-简单递归做法 | #小米Git#

class Solution {
public:
    int Git(vector<string>& matrix, int versionA, int versionB) {
        // write code here
        dfs(matrix, 0, versionA, versionB);
        return found;
    }
    int found = -1;
    int dfs(vector<string>& matrix, int node, int nodeA, int nodeB){
        if(found != -1) return 0;
        if(matrix[node][node] == -1) return 0; // visit
        int res = 0;
        if(node == nodeA) res |= 1;
        if(node == nodeB) res |= 2;
        matrix[node][node] = -1;
        for(int i = 0; i < matrix[node].size(); i++){
            if(matrix[node][i] == '1') res |= dfs(matrix, i, nodeA, nodeB);
        }
        if(found != -1){
            return res;
        }else{
            if(res == 3) found = node;
            return res;
        }
    }
};

经典最近公共祖先问题的

时间复杂度：O(n^2)，n为点的数量

空间复杂度：O(n)最大递归深度，n为点的数量