题解 | #农场牛群族谱#

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
        TreeNode pNode = findNode(root, p);
        TreeNode qNode = findNode(root, q);

        if (pNode == null || qNode == null) {
            return -1; // Nodes not found
        }

        TreeNode lcaNode = findLowestCommonAncestor(root, pNode, qNode);
        if (lcaNode != null) {
            return lcaNode.val;
        } else {
            return -1; // LCA not found
        }
    }

    private static TreeNode findNode(TreeNode root, int target) {
        if (root == null) {
            return null;
        }

        if (root.val == target) {
            return root;
        }

        TreeNode left = findNode(root.left, target);
        if (left != null) {
            return left;
        }

        TreeNode right = findNode(root.right, target);
        return right;
    }
    private static TreeNode findLowestCommonAncestor(TreeNode root, TreeNode p,
            TreeNode q) {
        if (root == null) {
            return null;
        }

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

        TreeNode left = findLowestCommonAncestor(root.left, p, q);
        TreeNode right = findLowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }
}

知识点：

1. 基本的Java语法和概念。
2. 二叉树的构建和遍历。
3. 递归算法的应用。

解题思路：

在lowestCommonAncestor方法中，我们首先使用findNode方法分别找到节点p和q在树中的位置。然后，我们调用findLowestCommonAncestor方法来查找节点p和q的最近公共祖先。

在findLowestCommonAncestor方法中，我们递归地在树中查找节点p和q的最近公共祖先。我们检查当前节点是否是p或q，如果是则返回当前节点。然后，我们在左子树和右子树中分别查找p和q的最近公共祖先。如果在左子树和右子树中都找到了非空的结果，说明当前节点就是最近公共祖先。如果只在其中一个子树中找到了结果，那么说明另一个节点在这个子树中，所以返回找到的节点。最后，如果两个子树都没找到结果，则返回null。