二叉树中寻找两个节点的最近公共祖先（LCA） - 递归方法详解

在二叉树中，寻找两个节点的最近公共祖先（Lowest Common Ancestor, LCA）是一个常见的问题。最近公共祖先是指在一个二叉树中，两个节点 p 和 q 的最深的公共祖先节点。

问题描述

给定一个二叉树和两个节点 p 和 q，找到它们的最近公共祖先。

解决方案

我们可以使用递归的方法来解决这个问题。递归的核心思想是：

1. 递归终止条件：

   • 如果当前节点为 null，返回 null。
   • 如果当前节点是 p 或 q，返回当前节点。

2. 递归过程：

   • 递归地在左子树中查找 p 和 q。
   • 递归地在右子树中查找 p 和 q。

3. 结果判断：

   • 如果左子树和右子树都返回了非 null 的节点，说明当前节点就是 p 和 q 的最近公共祖先。
   • 如果只有左子树返回了非 null 的节点，说明 p 和 q 都在左子树中，返回左子树的递归结果。
   • 如果只有右子树返回了非 null 的节点，说明 p 和 q 都在右子树中，返回右子树的递归结果。

代码实现

function lowestCommonAncestor(root, p, q) {
    // 递归终止条件
    if (root === null || root === p || root === q) {
        return root;
    }

    // 递归查找左子树和右子树
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);

    // 如果左右子树都找到了节点，说明当前节点是LCA
    if (left !== null && right !== null) {
        return root;
    }

    // 如果只有左子树找到了节点，返回左子树的结果
    if (left !== null) {
        return left;
    }

    // 如果只有右子树找到了节点，返回右子树的结果
    if (right !== null) {
        return right;
    }

    // 如果左右子树都没有找到节点，返回null
    return null;
}

示例

假设我们有以下二叉树：

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

• 节点 5 和 1 的最近公共祖先是 3。
• 节点 5 和 4 的最近公共祖先是 5。
• 节点 6 和 2 的最近公共祖先是 5。

时间复杂度

• 时间复杂度：O(N)，其中 N 是二叉树中节点的数量。在最坏情况下，我们需要访问所有节点。
• 空间复杂度：O(H)，其中 H 是二叉树的高度。递归调用栈的深度取决于树的高度。

总结

通过递归的方法，我们可以高效地找到二叉树中两个节点的最近公共祖先。这种方法不仅简洁，而且易于理解，是解决此类问题的经典方法。