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

二叉树中的最近公共祖先（LCA）问题要求找出给定两个节点在树中的最低（深度最大）的公共祖先节点。这个问题在数据库索引、版本控制系统（如Git）和编译器的语法分析等领域有重要应用。

问题描述
给定一棵二叉树和树中的两个节点p和q，找到它们的最近公共祖先。一个节点也可以是它自己的祖先。

解题思路分析
解决LCA问题有多种方法，我们将从简单方法开始，逐步优化到高效解法。

方法一：递归搜索（自底向上）
这是最直观的递归解法，通过深度优先搜索（DFS）遍历整棵树。

1. 基本思路：

   • 从根节点开始遍历整棵树
   • 如果当前节点是p或q，返回当前节点
   • 在左右子树中递归查找p和q
   • 根据左右子树的查找结果判断LCA

2. 具体步骤：

   • 如果当前节点为null，返回null
   • 如果当前节点是p或q，返回当前节点
   • 递归在左子树中查找p和q
   • 递归在右子树中查找p和q
   • 如果左右子树都找到了节点（即都不为null），说明当前节点就是LCA
   • 如果只有左子树找到了节点，返回左子树的结果
   • 如果只有右子树找到了节点，返回右子树的结果

3. 时间复杂度分析：

   • 最坏情况下需要遍历整棵树：O(n)
   • 空间复杂度：O(h)，其中h是树的高度

方法二：记录父节点路径
这种方法通过记录每个节点的父节点信息，然后比较两个节点的路径。

1. 基本思路：

   • 首先遍历整棵树，记录每个节点的父节点
   • 从p节点开始向上遍历到根节点，记录路径
   • 从q节点开始向上遍历，直到找到第一个在p路径中出现的节点

2. 具体实现步骤：

   • 使用哈希表存储每个节点的父节点指针
   • 从根节点开始进行BFS或DFS，填充父节点映射
   • 从p节点开始，使用集合记录所有祖先节点
   • 从q节点开始向上遍历，第一个出现在p祖先集合中的节点就是LCA

3. 复杂度分析：

   • 时间复杂度：O(n)用于构建父节点映射，O(h)用于查找路径
   • 空间复杂度：O(n)用于存储父节点映射和路径集合

方法三：Tarjan离线算法（进阶优化）
对于需要多次查询LCA的场景，可以使用更高效的Tarjan算法。

1. 算法思想：

   • 使用并查集（Union-Find）数据结构
   • 在深度优先遍历的过程中处理查询
   • 利用回溯时合并子树的特性

2. 实现步骤：

   • 初始化并查集，每个节点单独成集合
   • 对树进行后序遍历
   • 遍历完一个节点的子树后，将该子树与当前节点合并
   • 处理所有与该节点相关的查询

代码实现示例（方法一）

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    # 基准情况：空节点或找到目标节点
    if not root or root == p or root == q:
        return root
    
    # 在左子树中递归查找
    left = lowestCommonAncestor(root.left, p, q)
    # 在右子树中递归查找
    right = lowestCommonAncestor(root.right, p, q)
    
    # 如果左右子树都找到了节点，当前节点就是LCA
    if left and right:
        return root
    
    # 否则返回非空的那个结果
    return left if left else right

边界情况处理

1. 树为空的情况
2. p或q为null的情况
3. p和q是同一个节点
4. p或q不在树中的情况（需要额外验证）

算法选择建议

• 单次查询：使用方法一的递归解法，代码简洁高效
• 多次查询：使用Tarjan离线算法预处理
• 需要路径信息：使用方法二的路径记录法

这种方法确保了在各种情况下都能正确找到最近公共祖先，同时保持了较好的时间效率。