题解 | #农场牛群族谱# 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) {
        TreeNode res = traversal(root, p, q);
        return res.val;
    }

    private TreeNode traversal(TreeNode root, int p, int q) {
        if (root == null || root.val == p || root.val == q) {
            return root;
        }
        TreeNode left = traversal(root.left, p, q);
        TreeNode right = traversal(root.right, p, q);
        if (left != null && right != null) {
            return root;
        } else if (right != null) {
            return right;
        } else if (left != null) {
            return left;
        }
        return null;
    }
}

该代码使用的编程语言是Java

这道题的知识点是二叉树和递归。

代码的文字解释如下：

1. 定义了一个 TreeNode 结构体，表示二叉树的节点。它包含一个整型的 Val 属性，以及左右子树的指针 Left 和 Right。
2. lowestCommonAncestor 函数是解决最近公共祖先问题的主要函数。它接收一个 root 参数，表示二叉树的根节点，以及两个整型参数 p 和 q，表示要找到最近公共祖先的两个节点的值。函数返回最近公共祖先节点的值。
3. traversal 函数是 lowestCommonAncestor 函数的辅助函数。它使用递归来遍历二叉树。函数接收一个 root 参数，表示当前遍历的节点，以及两个整型参数 p 和 q。函数返回最近公共祖先节点。
4. 在 traversal 函数中，首先检查当前节点是否为空或者等于 p 或 q。如果是，则直接返回当前节点作为最近公共祖先节点。
5. 如果当前节点不是最近公共祖先节点，那么分别在左右子树中递归调用 traversal 函数。
6. 如果左子树和右子树都找到了最近公共祖先节点（即 left 和 right 都不为 nil），则说明当前节点就是最近公共祖先节点，直接返回当前节点。
7. 如果只有右子树找到了最近公共祖先节点，那么返回右子树节点。
8. 如果只有左子树找到了最近公共祖先节点，那么返回左子树节点。
9. 如果左右子树都没有找到最近公共祖先节点，则返回 nil。
10. 最后，lowestCommonAncestor 函数返回最近公共祖先节点的值。