JAVA二叉树的最近公共祖先

Java中二叉树的最近公共祖先可以通过递归来解决。首先，我们需要定义一个TreeNode类表示二叉树的节点，其中包含值和左右子节点的引用。下面是一个示例代码：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

接下来，我们可以实现一个递归函数来找到最近公共祖先：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 判断当前节点是否为空或者等于p或q
    if (root == null || root == p || root == q) {
        return root;
    }
    
    // 在左子树中寻找最近公共祖先
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    
    // 在右子树中寻找最近公共祖先
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    
    // 如果左子树和右子树都找到了最近公共祖先，则当前节点就是最近公共祖先
    if (left != null && right != null) {
        return root;
    }
    
    // 如果只有左子树找到了最近公共祖先，则返回左子树的结果
    if (left != null) {
        return left;
    }
    
    // 如果只有右子树找到了最近公共祖先，则返回右子树的结果
    if (right != null) {
        return right;
    }
    
    // 如果左右子树都没有找到最近公共祖先，则返回null
    return null;
}

这个递归函数的基本思路是：
- 当前节点为空或者等于p或q时，直接返回当前节点；
- 在左子树中寻找最近公共祖先；
- 在右子树中寻找最近公共祖先；
- 如果左子树和右子树都找到了最近公共祖先，则当前节点就是最近公共祖先；
- 如果只有左子树找到了最近公共祖先，则返回左子树的结果；
- 如果只有右子树找到了最近公共祖先，则返回右子树的结果；
- 如果左右子树都没有找到最近公共祖先，则返回null。

你可以调用这个函数来找到二叉树中任意两个节点的最近公共祖先。