求一棵树中两个节点的最近祖先（Java代码）

假设给了o1和o2两个节点（节点属于同一棵树中），求两个节点的最近公共祖先。
存在两种情况：
1）、o1是o2的祖先或者o2是o1的祖先
2）、两者都不是对方的祖先。

方法一：用HashMap和HashSet：先将o1的祖先串联起来，然后在遍历o2 的祖先，找到第一个与o1的祖先相同的节点就两者共同的最近祖先。

public static Node lowestAncestor(Node head, Node o1, Node o2){
    HashMap fatherMap = new HashMap<>();
    //特殊处理，头节点的父节点是自己
    fatherMap.put(head, head);
    process(head, fatherMap);
    HashSet set1 = new HashSet<>();
    
	Node cur = o1;
	//o1往上的所有的节点都链在set1里面
	while(cur != father.get(cur)){
		set1.add(cur);
		cur = fatherMap.get(cur);
	}
	set1.add(head);
	cur = o2;
	while(cur != fatherMap.get(cur））{
		if (!set1.add(cur){//如果cur在set1中，则add会返回一个false，表示添加失败。
			break; 
		}
		cur = fatherMap.get(cur);
	}
	return cur;
}
//将父子关系串起来
public static void process(Node head, HashMap fatherMap){
	if (head == null){
		return;
	}
	fatherMap.put(head.Left, head);
	fatherMap.put(head.Right, head);
	process(head.Left, fatherMap);
	process(head.Right, fatherMap);
}

方法二：递归：这个可以自己画一棵树来模拟一下。

public static Node lowestAncestor(Node head, Node o1, Node o2){
	if(head == null || head == o1 || head == o2){
		return head;
	}
	Node left = lowestAncestor(head.Left, o1, o2);
	Node right = lowestAncestor(head.Right, o1, o2);
	//o1和o2都不是对方的祖先
	if (left != null && right != null){
		return head;
	}
	//左右两棵树，并不都有返回值
	return left == null?right:left;
}