二叉树的最近公共祖先（Lowest Common Ancestor, LCA）问题

问题描述
给定一棵二叉树和两个节点p、q，要求找到这两个节点在树中的最近公共祖先。最近公共祖先的定义是：节点p和q在树中的最低（深度最大）的公共祖先节点。一个节点可以是自身的祖先。

解题思路
我们可以采用递归遍历的方法来解决这个问题。基本思路是：从根节点开始遍历整棵树，如果在当前子树中同时包含p和q，那么当前节点就是它们的公共祖先。我们需要找到深度最大的那个公共祖先。

详细步骤

1. 递归终止条件

   • 如果当前节点为null，返回null
   • 如果当前节点就是p或q，返回当前节点
   • 这是因为如果当前节点是p或q，那么它可能是公共祖先

2. 递归遍历左右子树

   • 对左子树进行递归搜索，得到左子树的结果
   • 对右子树进行递归搜索，得到右子树的结果

3. 分析递归结果

   • 如果左右子树的结果都不为null，说明p和q分别位于当前节点的左右子树中，当前节点就是LCA
   • 如果只有左子树结果不为null，说明p和q都在左子树中，返回左子树的结果
   • 如果只有右子树结果不为null，说明p和q都在右子树中，返回右子树的结果
   • 如果左右子树结果都为null，返回null

具体实现过程

让我们通过一个例子来理解这个过程：

考虑以下二叉树：

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

我们要找节点5和1的LCA。

递归过程分析：

1. 从根节点3开始：

   • 左子树递归：在节点5的子树中搜索
   • 右子树递归：在节点1的子树中搜索

2. 在节点5的子树中：

   • 节点5等于目标节点5，返回5

3. 在节点1的子树中：

   • 节点1等于目标节点1，返回1

4. 回到根节点3：

   • 左右子树都返回了非空值（5和1）
   • 根据规则，当前节点3就是LCA

另一个例子：找节点6和4的LCA

1. 从根节点3开始：

   • 左子树：在节点5的子树中搜索
   • 右子树：在节点1的子树中搜索（返回null，因为6和4都不在1的子树中）

2. 在节点5的子树中：

   • 左子树：在节点6的子树中搜索（节点6等于目标节点6，返回6）
   • 右子树：在节点2的子树中搜索

3. 在节点2的子树中：

   • 左子树：在节点7的子树中搜索（返回null）
   • 右子树：在节点4的子树中搜索（节点4等于目标节点4，返回4）
   • 节点2收到左右子树的结果：左null，右4
   • 由于右子树有结果，返回4

4. 回到节点5：

   • 左子树返回6，右子树返回4
   • 左右都不为null，所以节点5就是LCA

时间复杂度分析

• 每个节点最多被访问一次
• 时间复杂度：O(n)，其中n是树中的节点数
• 空间复杂度：O(h)，其中h是树的高度（递归栈的深度）

特殊情况处理

• 如果p或q不在树中，算法仍然能正确工作
• 如果p是q的祖先（或反之），算法也能正确识别

这种方法利用了二叉树递归遍历的特性，通过后序遍历（左右根的顺序）来找到最低的公共祖先节点。