题解 | #在二叉树中找到两个节点的最近公共祖先#

使用bfs搜索左右子树，由于bfs特性，能优先找到深度最低的节点。 如果o1,o2在当前子树的左右子树上，那么就返回为空的那项。 如果o1,o2都在左子树或者右子树上，那么就返回不为空的节点。

import java.util.*;

public class Solution {
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        return pre(root,o1,o2).val;
    }
    public TreeNode pre(TreeNode root, int o1 , int o2){
        if(root==null || root.val==o1 || root.val==o2)
            return root;
        TreeNode left  = pre(root.left,o1,o2);
        TreeNode right = pre(root.right,o1,o2);
        if(null!=left && null!=right)
            return root;
        return null==left?right:left;
    }
}