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

思路：

第一步：找左子树上有没有两值，有就继续像左子树递归，没有就第二步

第二步：找右子树有没有两值，有就向右子树递归，没有就第三步

第三步：说明两值分别在左右子树上，则当前值就是公共祖先

/*
 * 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) {
        // write code here
        boolean h= isHas(root.left,o1)&&isHas(root.left,o2);
        if (h){
            return lowestCommonAncestor(root.left,o1,o2);
        }
        h=isHas(root.right,o1)&&isHas(root.right,o2);
        if (h){
            return lowestCommonAncestor(root.right,o1,o2);
        }
        return root.val;
    }
    private static boolean isHas(TreeNode root, int o1) {
        if (root==null){
            return false;
        }
        if (root.val==o1){
            return true;
        }else{
            return isHas(root.left,o1)||isHas(root.right,o1);
        }
    }
}