题解 | #两个普通二叉树的第一个公共祖先结点#

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) {
        //一左一右
        if(has(root.left,o1)&&has(root.right,o2)||has(root.left,o2)&&has(root.right,o1)) {
            return root.val ;//就是当前节点
        }
        //双左
        if(has(root.left,o1)&&has(root.left,o2)) {
            if(root.left.val == o1 || root.left.val == o2) {//有一个就是左节点，那返回左节点
                return root.left.val ;
            } else {//去左子树查找
                return lowestCommonAncestor(root.left , o1 , o2) ;
            }
        }
        //双右
        if(has(root.right,o1)&&has(root.right,o2)) {
            if(root.right.val == o1 || root.right.val == o2) {
                return root.right.val ;
            } else {
                return lowestCommonAncestor(root.right , o1 , o2) ;
            }
        }
        //其他
        return -1 ;
        
    }
    
    //在二叉树中查找是否含有n
    public boolean has(TreeNode root , int n) {
        if(root == null) {
            return false ;
        }
        if(root.val == n) {
            return true ;
        } else {
            return has(root.left , n) || has(root.right,n) ;
        }
    }
}