题解 | #小米Git# BFS建树、DFS搜索

1、使用BFS构建树

2、使用DFS搜索树并得到两个节点各自的路径

3、对比路径找到最后一个公共祖先

#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>
class Solution {
  private:
    // 使用BFS构建树
    unordered_map<int, vector<int>> BFS(vector<string>& matrix) {
        unordered_map<int, vector<int>> mp;
        queue<int> qu;
        qu.push(0);
        unordered_set<int> visited; // 记录已访问过的节点
        visited.insert(0);
        while (!qu.empty()) {
            int node = qu.front();
            qu.pop();
            for (int i = 0; i < matrix.size(); i++) {
                if (matrix[node][i] == '1' && visited.find(i) == visited.end()) {
                    visited.insert(i);
                    qu.push(i);
                    mp[node].push_back(i); // 哈希表中加入子节点
                }
            }
        }
        return mp;
    }

    //使用DFS搜索树
    void DFS(unordered_map<int, vector<int>>& mp, vector<int>& path, int curr,
             int target) {
        // 当路径存在且最后一个访问的节点为目标节点时提前返回
        if (path.size() != 0 && path.back() == target) {
            return;
        }
        path.push_back(curr);
        if (curr == target) {
            return;
        }
        for (const auto& x : mp[curr]) {
            DFS(mp, path, x, target);
        }
        // 未找到target时回溯
        if (path.back() != target) {
            path.pop_back();
        }
    }

  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix string字符串vector
     * @param versionA int整型
     * @param versionB int整型
     * @return int整型
     */
    int Git(vector<string>& matrix, int versionA, int versionB) {
        if (versionA == versionB || matrix.size() == 1) {
            return versionA;
        }
        unordered_map<int, vector<int>> mp = BFS(matrix);
        vector<int> pathA, pathB; // 分别记录A和B的寻找路径
        DFS(mp, pathA, 0, versionA);
        DFS(mp, pathB, 0, versionB);
        int ans = 0;
        for (int i = 0; i < pathA.size() && i < pathB.size(); i++) {
            // 找到最后一个相同的路径节点，即为最近父节点
            if (pathA[i] == pathB[i]) {
                ans = pathA[i];
            } else {
                break;
            }
        }
        return ans;
    }
};