找二叉数中两个节点的最低公共祖先节点

给定两个二叉树的节点node1 ， node2 找到他们的最低公共祖先节点

public Node f(Node head , Node node1 , Node node2){
	HashMap<Node , Node> hashMap =  new HashMap();
	hashMap.put(head , head);
	pross(head , hashMap);
	HashSet<Node> set1 = new HashSet();
	Node cur = node1;
	while(cur != hashMap.get(cur)){
		set1.add(cur);
		cur = hashMap.get(cur); 
	}
	set1.add(head);
	while(!set1.contains(node2)){
		 node2 = hashMap.get(node2); 
	}
	return node2;
} 
public void pross(Node head , HashMap<Node , Node> hashMap){
	if(head == null){
		return null; 
	}
	hashMap.put(head.left , head);
	hashMap.put(head.right , head);
	pross(head.left , hashMap);
	pross(head.right , hashMap);
}

还有一种方法比较难以理解

public Node f(Node  head , Node node1 , Node node2){
	if(head == null || head == node1 || head == node2){
		return head;
 	}
 	Node left  = f(head.left , node1 , node2);
	Node right = f(head.right , node1 , node2);
	if(left != null && right != null){
		return head; 
	}
	return left != null ? left : right;
}