求树上lca

这里没有采用倍增的方法, 直接dfs求depth数组和fa数组即可

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 整型
     */
    static const int N = 1024;
    int n, ia, ib;
    int depth[N], fa[N];
    vector<vector<int>> g;
        
    void dfs(int u, int p, int d) {
        if(depth[u] != -1) return;
        depth[u] = d;
        fa[u] = p;
        for(auto v : g[u]) {
            if(v == p) continue;
            dfs(v, u, d+1);
        }
    }
    
    int getSplitNode(vector<string> matrix, int indexA, int indexB) {
        n = matrix.size();
        g.resize(n);
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(matrix[i][j] == '1') 
                    g[i].push_back(j), g[j].push_back(i);
            }
        }
        memset(depth, -1, sizeof depth), memset(fa, -1, sizeof fa);
        dfs(0, -1, 0);
        while(depth[indexA] > depth[indexB]) {
            indexA = fa[indexA];
        }
        while(depth[indexA] < depth[indexB]) {
            indexB = fa[indexB];
        }
        while(indexA != indexB) {
            indexA = fa[indexA], indexB = fa[indexB];
        }
        return indexA;
    }
};