关于公共祖先的问题分类：
这类问题有多种解法和类型，根据题目给出的信息去判断使用哪一种
1、给你树，只支持从父亲找儿子，不支持儿子找父亲，最后要求最近公共祖先，使用dfs或者分治
2、支持儿子找父亲，求最近公共祖先，逆序，从儿子找到底，然后比较（具体看本题代码，说不清）
3、不给树，求是否有共同祖先，并查集
4、还有离线、倍增等方法、
本题属于第二种：
1、从儿子找到底，把两条路径都记录下来
2、从后往前比对两条路径，从那里开始不一样，前一个就是最近的公共祖先
3、注意需要把自己也放进路径中，因为自己可能已经是别人的父亲了
4、使用map存放儿子-》父亲的关系比较好用，因为一个孩子只能有一个父亲。
代码如下：
import java.util.HashMap;
import java.util.Scanner; public class Main { public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int testCase = cin.nextInt();
for (int i = 0; i < testCase; i++){
int n = cin.nextInt();
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for (int j = 0; j < n-1; j++){
int parent = cin.nextInt();
int child = cin.nextInt();
map.put(child,parent);
}
int nodeOne = cin.nextInt();
int nodeTwo = cin.nextInt();
System.out.println(nca(nodeOne, nodeTwo, map, n));
}
} private static int nca(int nodeOne, int nodeTwo, HashMap<Integer,Integer> map, int maxLength){
int[] nodeOneArray = new int[maxLength];
nodeOneArray[0] = nodeOne;
int nodeOneIndex = 1;
while (map.containsKey(nodeOne)){
nodeOneArray[nodeOneIndex] = map.get(nodeOne);
nodeOne = nodeOneArray[nodeOneIndex];
nodeOneIndex++;
} int[] nodeTwoArray = new int[maxLength];
nodeTwoArray[0] = nodeTwo;
int nodeTwoIndex = 1;
while (map.containsKey(nodeTwo)){
nodeTwoArray[nodeTwoIndex] = map.get(nodeTwo);
nodeTwo = nodeTwoArray[nodeTwoIndex];
nodeTwoIndex++;
} nodeOneIndex--;
nodeTwoIndex--;
while (nodeOneArray[nodeOneIndex] == nodeTwoArray[nodeTwoIndex]){
nodeOneIndex--;
nodeTwoIndex--;
if (nodeOneIndex == -1){
return nodeOneArray[nodeOneIndex+1];
} else if (nodeTwoIndex == -1){
return nodeTwoArray[nodeTwoIndex+1];
}
}
return nodeOneArray[nodeOneIndex+1];
}
}