本文共 1315 字，大约阅读时间需要 4 分钟。

为了找到二叉树中两个指定节点的最近公共祖先，我们可以采用递归的方法，分别检查左右子树，直到找到共同的祖先节点。以下是详细的实现步骤：

以下是基于上述逻辑的实现代码：

class Solution5 {    public TreeNode2 lowestCommonAncestor(TreeNode2 root, TreeNode2 p, TreeNode2 q) {        if (root == null) {            return null;        }        if (root == p || root == q) {            return root;        }        TreeNode2 leftP = lowestCommonAncestor(root.left, p, q);        TreeNode2 leftQ = lowestCommonAncestor(root.left, p, q);        TreeNode2 rightP = lowestCommonAncestor(root.right, p, q);        TreeNode2 rightQ = lowestCommonAncestor(root.right, p, q);        if (leftP != null && rightQ != null) {            return root;        } else if (leftP != null) {            return leftP;        } else if (rightQ != null) {            return rightQ;        } else {            return null;        }    }}

步骤解释：

• 检查当前节点是否为空：如果根节点为空，调用函数返回null。
• 检查当前节点是否为目标节点：如果当前节点是p或q，直接返回当前节点作为最近公共祖先。
• 递归查找左子树：分别从左子树中查找p和q的最近公共祖先。
• 递归查找右子树：分别从右子树中查找p和q的最近公共祖先。
• 判断返回结果：
  • 如果左子树和右子树都有结果，说明最近公共祖先在根节点。
  • 如果只有左子树有结果，返回左子树的结果。
  • 如果只有右子树有结果，返回右子树的结果。
  • 如果左右子树都没有结果，返回null。

这种方法通过递归分别检查左右子树，确保了找到最近公共祖先的准确性和效率。

转载地址：http://xdrnz.baihongyu.com/