题解 | #层序遍历：小米Git #

这个题目主要考察的是层序遍历写法，确定父节点就好了

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix string字符串vector 
     * @param versionA int整型 
     * @param versionB int整型 
     * @return int整型
     */
    pair<vector<int>, vector<int>> findFatherNodes(vector<string>& matrix, int versionA, int versionB) {
        vector<int> ans(matrix.size(), -1);
        map<int, int> dict;
        // 层次遍历找到父节点
        queue<int> nodeQue;
        nodeQue.push(0);
        while (!nodeQue.empty()) {
            int i = nodeQue.front();
            nodeQue.pop();
            dict[i] = 1;
            // 找到 node 节点的所有子节点
            for (int j=0; j<matrix[i].size(); j++) {
                if (matrix[i][j] == '1' && !dict[j]) {
                    nodeQue.push(j);
                    ans[j] = i;              // 父节点为 i 
                }
            }
        }
        
        
        // 找到 A 的所有父节点
        vector<int> faNodesA={versionA}, faNodesB={versionB};
        while( ans[versionA] != -1) {
            faNodesA.push_back(ans[versionA]);
            versionA = ans[versionA];
        }
        // 找到 B 的所有父节点
        while ( ans[versionB] != -1 ) {
            faNodesB.push_back(ans[versionB]);
            versionB = ans[versionB];
        }
        return {faNodesA, faNodesB};
    }
    
    int findMinPubNodes(vector<int> faNodesA, vector<int> faNodesB) {
        // 公共节点
        int i = faNodesA.size()-1, j = faNodesB.size()-1; int pubNode;
        while (faNodesA[i] == faNodesB[j]) {
            if (i<0 || j<0) break;
            pubNode = faNodesA[i];
            i--;
            j--;
        }
        return pubNode;
    }
    
    
    int Git(vector<string>& matrix, int versionA, int versionB) {
        // 层次遍历找到两个节点的所有根节点
        pair<vector<int>, vector<int>> faNodesAB = findFatherNodes(matrix, versionA, versionB);
        return findMinPubNodes(faNodesAB.first, faNodesAB.second);
    }
};