LCA算法详解（使用Python实现最近公共祖先查找）

为什么需要LCA算法？

LCA算法广泛应用于：

• 文件系统路径比较
• 社交网络中两个人的最近共同联系人
• 基因谱系分析
• 编译器中的语法树优化

准备工作：定义二叉树节点

在实现LCA之前，我们先定义一个简单的二叉树节点类：

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

方法一：递归法实现LCA（适用于普通二叉树）

这是最直观的方法。我们从根节点开始递归搜索：

• 如果当前节点是 p 或 q，说明找到了目标节点之一
• 递归搜索左右子树
• 如果左右子树都返回非空，说明当前节点就是LCA

def lowestCommonAncestor(root, p, q):    # 基本情况：如果根为空，或者根是p或q    if not root or root == p or root == q:        return root        # 递归查找左子树和右子树    left = lowestCommonAncestor(root.left, p, q)    right = lowestCommonAncestor(root.right, p, q)        # 如果左右都不为空，说明p和q分别在左右子树，当前root就是LCA    if left and right:        return root        # 否则返回非空的那个（可能都在左子树或都在右子树）    return left if left else right  

方法二：使用父指针（适用于已知父节点的情况）

如果我们能访问每个节点的父节点，可以先记录从p到根的路径，再从q向上遍历，第一个出现在p路径中的节点就是LCA。

def lowestCommonAncestorWithParent(root, p, q):    # 构建父指针字典    parent = {root: None}    stack = [root]        # BFS构建父关系    while p not in parent or q not in parent:        node = stack.pop()        if node.left:            parent[node.left] = node            stack.append(node.left)        if node.right:            parent[node.right] = node            stack.append(node.right)        # 获取p到根的路径    ancestors = set()    while p:        ancestors.add(p)        p = parent[p]        # 从q向上找，第一个在ancestors中的就是LCA    while q not in ancestors:        q = parent[q]    return q  

完整示例：运行你的第一个LCA程序

下面是一个完整的可运行示例：

# 定义树节点class TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = right# LCA函数def lowestCommonAncestor(root, p, q):    if not root or root == p or root == q:        return root    left = lowestCommonAncestor(root.left, p, q)    right = lowestCommonAncestor(root.right, p, q)    if left and right:        return root    return left if left else right# 构建测试树#       3#      / \#     5   1#    / \ / \#   6  2 0  8#     / \#    7   4root = TreeNode(3)root.left = TreeNode(5)root.right = TreeNode(1)root.left.left = TreeNode(6)root.left.right = TreeNode(2)root.right.left = TreeNode(0)root.right.right = TreeNode(8)root.left.right.left = TreeNode(7)root.left.right.right = TreeNode(4)# 查找节点5和节点1的LCAp = root.left  # 节点5q = root.right # 节点1lca = lowestCommonAncestor(root, p, q)print(f"LCA of {p.val} and {q.val} is {lca.val}")  # 输出: LCA of 5 and 1 is 3  

总结

通过本文，你已经掌握了如何用Python实现LCA算法来查找二叉树中两个节点的最近公共祖先。递归方法简洁高效，适合大多数面试和实际应用场景。希望这篇教程能帮助你理解LCA算法的核心思想，并能在项目中灵活运用！

提示：多动手写代码、画树结构图，是掌握LCA算法的最佳方式。