题解 | #小米Git#

1.先对数据进行预处理，生成邻接表 2.再对图（也可以理解成多叉树，但是没有方向）进行层序遍历，拿到自定向下的结点顺序 3.外层负责确定接下来作为根结点处理的结点，内层负责对根节点直接关联的子节点构成的子树进行目标查找。 注意：存在情况，子树同时包含两个目标，这时候公共根结点应该为子树的某个结点，而非root。因此需要引入tmpfindA和tmpfindB，它们是判断与root直接关联的子结点构成的子树中是否包含目标的依据；findA和findB是判断root能否成为公共结点的依据。

import java.util.*;

public class Solution {
    public static int findA;
    public static int findB;
    public static ArrayList<Integer> visitedNode;//辅助构建有向图
    public int Git (String[] matrix, int versionA, int versionB) {
        //1.将字符数组转换成邻接表
        int[][] arr = new int[matrix.length][matrix[0].length()];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length(); j++) {
                arr[i][j] = matrix[i].charAt(j) - '0';
            }
        }
      
        //2.层序遍历，存储自顶向下自左向右顺序的结点集合。作用是，为下面每个结点作为根结点进行处理提供顺序。确保了上层结点优先作为根节点进行处理。
        ArrayList<Integer> list = new ArrayList<>();
        layOrder(arr,list);
      
        //用于存储处理完毕的根节点
        visitedNode = new ArrayList<>();
      
      	//3.将邻接表中每一个结点作为根节点进行一次处理，判断是否能够成为公共结点。
        for(int i=0;i<list.size();i++){
            visitedNode.add(list.get(i));//存入集合，表示已作为根节点进行访问
            //-1表示未找到目标，这两个变量主要为当前结点作为根的子树服务。提供root是否能够成为公共结点的依据。
            findA = -1;
            findB = -1;
            int root = list.get(i);//i表示当前root在list中的下标
            if(root == versionA || root == versionB){
                return root;//作为根节点，root已经匹配某个目标，那么另一个目标必然存在于以root为根的多叉树中，root必然是公共结点。
            }
            //处理root直接关联的子结点
            for(int j=0;j<arr[root].length;j++){
                //记录当前直接关联的子节点构成的子树经过dfs后的结果
                int tmpfindA = findA;
                int tmpfindB = findB;
                if(arr[root][j] == 1){
                    dfs(arr,j,versionA,versionB,new boolean[arr.length]);
                }
              	//两个临时变量都发生了改变，说明这棵子节点构成的子树包含两个目标，而root不是公共父节点。因此需要重置findA、B，避免误判root为公共节点
                if(tmpfindA != findA && tmpfindB != findB){
                    findA = -1;
                    findB = -1;//重置等待下次这个子节点j作为root时再处理
                }
            }
          	//两个变量都发生了改变，说明两个目标分别在root的两棵子树
            if(findA != -1 && findB != -1){
                return root;
            }
          	//只有一个发生改变，说明两个部门在同一条枝上，因此先发现的目标的那个位置即公共节点。可能是A先被发现，也可能是B先被发现。
            if(findA != -1){
                return findA;
            }
            if(findB != -1){
                return findB;
            }
        }
        return 0;
    }
  	//搜索是否存在目标，只要搜索到一个目标，当前分支后面的搜索将不再进行。
    public static void dfs(int[][] arr, int curNode, int versionA, int versionB,
                           boolean[] visited) {
        visited[curNode] = true;
        if (curNode == versionA) {
            findA = curNode;
            return;
        }
        if (curNode == versionB) {
            findB = curNode;
            return;
        }
        for(int i=0;i<arr[curNode].length;i++){
            //visitedNode作用是防止向上dfs
            if(visited[i] == false && !visitedNode.contains(i) && i != curNode && arr[curNode][i] == 1){
                dfs(arr,i,versionA,versionB,visited);
            }
        }
    }
  	//层序遍历
    public static void layOrder(int[][] arr,ArrayList<Integer> list){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        list.add(0);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0;i<size;i++){
                int node = queue.poll();
                for(int j=0;j<arr[node].length;j++){
                    if(arr[node][j] == 1 && !list.contains(j)){
                        queue.offer(j);
                        list.add(j);
                    }
                }
            }
        }
    }
}