非递归写法
要想找到两个节点的最近公共祖先节点，我们可以从两个节点往上找，每个节点都往上走，一直走到根节点，那么根节点到这两个节点的连线肯定有相交的地方，如果是从上往下走，那么最后一次相交的节点就是他们的最近公共祖先节点。我们就以找6和7的最近公共节点来画个图看一下
我们看到6和7公共祖先有5和3，但最近的是5。我们只要往上找，找到他们第一个相同的公共祖先节点即可，但怎么找到每个节点的父节点呢，我们只需要把每个节点都遍历一遍，然后顺便记录他们的父节点存储在Map中。我们先找到其中的一条路径，比如6→5→3，然后在另一个节点往上找，由于7不在那条路径上，我们找7的父节点是2，2也不在那条路径上，我们接着往上找，2的父节点是5，5在那条路径上，所以5就是他们的最近公共子节点。
其实这里我们可以优化一下，我们没必要遍历所有的结点，我们一层一层的遍历（也就是BFS），只需要这两个节点都遍历到就可以了，比如上面2和8的公共结点，我们只需要遍历到第3层，把2和8都遍历到就行了，没必要再遍历第4层了。（BFS就是一层一层的遍历，如下图所示）
我们来看下代码
public int lowestCommonAncestor(TreeNode root, int o1, int o2) {
//记录遍历到的每个节点的父节点。
Map<Integer, Integer> parent = new HashMap<>();
Queue<TreeNode> queue = new LinkedList<>();
parent.put(root.val, Integer.MIN_VALUE);//根节点没有父节点，给他默认一个值
queue.add(root);
//直到两个节点都找到为止。
while (!parent.containsKey(o1) || !parent.containsKey(o2)) {
//队列是一边进一边出，这里poll方法是出队，
TreeNode node = queue.poll();
if (node.left != null) {
//左子节点不为空，记录下他的父节点
parent.put(node.left.val, node.val);
//左子节点不为空，把它加入到队列中
queue.add(node.left);
}
//右节点同上
if (node.right != null) {
parent.put(node.right.val, node.val);
queue.add(node.right);
}
}
Set<Integer> ancestors = new HashSet<>();
//记录下o1和他的祖先节点，从o1节点开始一直到根节点。
while (parent.containsKey(o1)) {
ancestors.add(o1);
o1 = parent.get(o1);
}
//查看o1和他的祖先节点是否包含o2节点，如果不包含再看是否包含o2的父节点……
while (!ancestors.contains(o2))
o2 = parent.get(o2);
return o2;
} 时间复杂度：O（n），n是二叉树节点的个数，最坏情况下每个节点都会被访问一遍
空间复杂度：O（n），一个是BFS需要的队列，一个是父子节点关系的map
看下运行结果
递归写法
这题我们还可以改一下，使用递归的写法，代码中有注释，就不在详细介绍。
public int lowestCommonAncestor(TreeNode root, int o1, int o2) {
return helper(root, o1, o2).val;
}
public TreeNode helper(TreeNode root, int o1, int o2) {
if (root == null || root.val == o1 || root.val == o2)
return root;
TreeNode left = helper(root.left, o1, o2);
TreeNode right = helper(root.right, o1, o2);
//如果left为空，说明这两个节点在root结点的右子树上，我们只需要返回右子树查找的结果即可
if (left == null)
return right;
//同上
if (right == null)
return left;
//如果left和right都不为空，说明这两个节点一个在root的左子树上一个在root的右子树上，
//我们只需要返回cur结点即可。
return root;
} 时间复杂度：O（n），n是二叉树节点的个数，最坏情况下每个节点都会被访问一遍
空间复杂度：O（n），因为是递归，取决于栈的深度，最差最差情况下，二叉树退化成链表，栈的深度是n。
看一下运行结果
截止到目前我在公众号“数据结构和算法”中已经写了500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
京公网安备 11010502036488号