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为点的数量