Java 题解 | #农场牛群族谱#

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) {
        if (root == null) {
            return -1;
        }

        if (root.val == p || root.val == q) {
            return root.val;
        }

        int left = lowestCommonAncestor(root.left, p, q);
        int right = lowestCommonAncestor(root.right, p, q);

        if (left > 0 && right > 0) {
            return root.val;
        }

        return left == -1 ? right : left;
    }
}

该代码采用的编程语言是Java。

考察以下知识点：

1. 二叉树的遍历和递归：代码中使用递归的方式遍历二叉树，分别在左子树和右子树中查找最低公共祖先。
2. 二叉树节点定义和构建：代码中使用了一个自定义的 TreeNode 类来表示二叉树的节点，并使用构造函数初始化节点对象。
3. 逻辑判断和条件语句：代码中使用了逻辑判断语句 if 和三元运算符 ?: 来进行条件判断和返回结果。
4. 递归终止条件：通过判断节点是否为空，以及节点值是否等于目标值，来确定递归的终止条件。

代码的文字解释大纲如下：

1. 首先定义一个 TreeNode 类，表示二叉树的节点，包含一个整型的 val 属性以及左右子节点的引用。
2. 在 Solution 类中定义一个方法 lowestCommonAncestor，接收一个二叉树的根节点 root 和两个目标值 p、q。
3. 先对特殊情况进行处理，如果根节点为空，则返回 -1 表示未找到最低公共祖先。
4. 对根节点的值进行判断，如果等于目标值之一，则说明当前根节点就是最低公共祖先，直接返回当前节点值。
5. 否则，分别递归地在左子树和右子树中查找目标值的最低公共祖先，将结果保存在 left 和 right 变量中。
6. 根据 left 和 right 的值进行判断：如果 left 和 right 都大于 0，则说明 p 和 q 分别位于当前节点的左右子树中，当前节点就是它们的最低公共祖先，返回当前节点的值。如果 left 的值为 -1，则说明 p 和 q 都不在左子树中，返回 right 的值作为最低公共祖先。如果 right 的值为 -1，则说明 p 和 q 都不在右子树中，返回 left 的值作为最低公共祖先。