二叉树的最近公共祖先

二叉树的最近公共祖先是指在以根节点为根的二叉树中，找到并返回给定节点p和节点q的最近共同祖先节点。根据递归函数的定义，我们可以通过以下步骤找到最近公共祖先节点：

1. 终止条件：如果根节点为空，或者根节点等于p或q，则直接返回根节点。

2. 递归调用：分别对根节点的左子树和右子树调用递归函数lowestCommonAncestor，传入节点p和节点q。

3. 分情况讨论：

- 如果节点p和节点q分别存在于根节点的左右子树中（异侧），则根节点即为最近公共祖先节点。
- 如果节点p和节点q都在根节点的左子树中，递归调用函数lowestCommonAncestor(root.left, p, q)，返回的结果即为最近公共祖先节点。
- 如果节点p和节点q都在根节点的右子树中，递归调用函数lowestCommonAncestor(root.right, p, q)，返回的结果即为最近公共祖先节点。

4. 返回结果：根据左右子树的返回结果，进行判断：

- 如果左子树和右子树的返回结果都不为空，说明节点p和节点q分别存在于根节点的左右子树中，那么根节点即为最近公共祖先节点。
- 如果左子树的返回结果为空，说明节点p和节点q都在根节点的右子树中，那么右子树的返回结果即为最近公共祖先节点。
- 如果右子树的返回结果为空，说明节点p和节点q都在根节点的左子树中，那么左子树的返回结果即为最近公共祖先节点。

下面是相应的代码实现：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode 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;
    } else if (left == null) {
        return right;
    } else if (right == null) {
        return left;
    } else {
        return null;
    }
}