题解 | #农场牛群族谱#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        return commonAncestor(root, p, q).val;
    }
    private TreeNode commonAncestor(TreeNode root, int p, int q) {
	  	// 递归结束条件
        if (root == null || root.val == p || root.val == q) return root;
	  	// 分别递归左右子树，查找公共祖先
        TreeNode left = commonAncestor(root.left, p, q);
        TreeNode right = commonAncestor(root.right, p, q);
        if (left == null) return right;		// 如果左子树没有，就返回右子树
        if (right == null) return left;		// 如果右子树没有，就返回左子树
        return root;	// 都没有，则返回根节点
    }
}