题解转载于数据结构和算法的博客
非递归写法
要想找到两个节点的最近公共祖先节点，我们可以从两个节点往上找，每个节点都往上走，一直走到根节点，那么根节点到这两个节点的连线肯定有相交的地方，如果是从上往下走，那么最后一次相交的节点就是他们的最近公共祖先节点。我们就以找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就是一层一层的遍历，如下图所示）
图片说明
时间复杂度：O（n），n是二叉树节点的个数，最坏情况下每个节点都会被访问一遍
空间复杂度：O（n），一个是BFS需要的队列，一个是父子节点关系的map

方法2:
递归写法
这题我们还可以改一下，使用递归的写法，代码中有注释，就不在详细介绍。
时间复杂度：O（n），n是二叉树节点的个数，最坏情况下每个节点都会被访问一遍
空间复杂度：O（n），因为是递归，取决于栈的深度，最差最差情况下，二叉树退化成链表，栈的深度是n。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {

    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {

        //注：本题保证二叉树中每个节点的val值均不相同。所以递归没有问题
        return treeDeep(root, o1, o2).val;

//         return treeDeep2(root, o1, o2);

    }

    public TreeNode treeDeep (TreeNode root, int o1, int o2) {

        if (root == null) {
            return root;
        }

        if (root.val == o1 || root.val == o2) {
            return root;
        }

        TreeNode left = treeDeep(root.left, o1, o2);
        TreeNode right = treeDeep(root.right, o1, o2);

        //如果left为空，说明这两个节点在root结点的右子树上，我们只需要返回右子树查找的结果即可
        if (left == null) {
            return right;
        }

        //同上
        if (right == null) {
            return left;
        }

        //如果left和right都不为空，说明这两个节点一个在root的左子树上一个在root的右子树上，
        //我们只需要返回cur结点即可。
        return root;
    }

    public int treeDeep2 (TreeNode root, int o1, int o2) {

        //方法2:注：本题保证二叉树中每个节点的val值均不相同。所以可以使用map来保存子节点->父节点的对应关系
        Map<Integer, Integer> map = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        //根节点没有父节点，给他默认一个值
        map.put(root.val, Integer.MIN_VALUE);
        queue.add(root);

        while (!map.containsKey(o1) || !map.containsKey(o2)) {

            TreeNode node = queue.poll();

            if (node.left != null) {
                //存入该节点的父子关系
                map.put(node.left.val, node.val);
                queue.add(node.left);
            }

            if (node.right != null) {
                //存入该节点的父子关系
                map.put(node.right.val, node.val);
                queue.add(node.right);
            }
        }

        Set<Integer> ancestors = new HashSet<>();

        //记录下o1和他的祖先节点，从o1节点开始一直到根节点。
        while (map.containsKey(o1)) {
            ancestors.add(o1);
            o1 = map.get(o1);
        }

        //查看o1和他的祖先节点是否包含o2节点，如果不包含再看是否包含o2的父节点……
        while (!ancestors.contains(o2)) {
            o2 = map.get(o2);
        }

        return o2;
    }
}