忍者算法

Appearance

【忍者算法】从家族树到二叉树：深入解析最近公共祖先问题｜LeetCode 236 二叉树的最近公共祖先 ​

从生活场景理解LCA ​

想象你在整理家族族谱时，需要找到两位家族成员的最近共同祖先。比如小明和小红，他们的最近共同祖父可能不是年龄最大的祖先，而是离他们最近的共同长辈。在计算机科学中，二叉树中的最近公共祖先（LCA）问题与此如出一辙。

问题解析 ​

LeetCode第236题要求：给定一个二叉树和两个节点p、q，找到这两个节点在树中的最近公共祖先。注意：

  1. 节点可以是自身的祖先
  2. p和q都存在于二叉树中
  3. 所有节点值唯一

递归法：优雅的分治策略 ​

递归思路分解 ​

我们可以把问题分解为三个层次来思考：

  1. 当前节点是否是p或q？
  2. 目标节点是否在左子树？
  3. 目标节点是否在右子树？

当出现以下情况之一时，当前节点就是LCA：

  • p和q分别位于左右子树（即左右递归都返回非空）
  • 当前节点是p/q，且另一个节点在其子树中
java
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 递归终止条件：找到目标节点或遍历到空节点
        if (root == null || root == p || root == q) return root;
        
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        // 左右子树都找到目标节点，当前节点就是LCA
        if (left != null && right != null) return root;
        
        // 单边找到目标节点则向上传递
        return left != null ? left : right;
    }
}

递归过程图解 ​

以二叉树[3,5,1,6,2,0,8,null,null,7,4]为例，寻找节点5和1的LCA：

        3
      /   \
     5     1   ← LCA是3
    / \   / \
   6  2 0   8
     / \
    7  4

递归执行过程：

  1. 根节点3不是目标节点，递归左右子树
  2. 左子树5发现目标节点，右子树1发现另一个目标节点
  3. 根据判断条件，返回根节点3作为LCA

迭代法：显式记录访问路径 ​

虽然递归法简洁优雅，但可能有读者更习惯迭代思维。我们可以通过记录访问路径的方式实现：

实现步骤 ​

  1. 使用哈希表存储每个节点的父指针
  2. 记录从p到根节点的访问路径
  3. 从q出发向上查找，第一个出现在p路径中的节点即为LCA
java
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 建立父指针映射
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        parent.put(root, null);
        stack.push(root);

        // 构建完整父指针表
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.left != null) {
                parent.put(node.left, node);
                stack.push(node.left);
            }
            if (node.right != null) {
                parent.put(node.right, node);
                stack.push(node.right);
            }
        }

        // 记录p的访问路径
        Set<TreeNode> ancestors = new HashSet<>();
        while (p != null) {
            ancestors.add(p);
            p = parent.get(p);
        }

        // 查找q路径中的第一个公共节点
        while (!ancestors.contains(q)) {
            q = parent.get(q);
        }
        return q;
    }
}

方法对比 ​

方法时间复杂度空间复杂度实现难度
递归法O(n)O(h)★★☆☆☆
迭代法O(n)O(n)★★★☆☆

递归法凭借其简洁性成为首选方案，迭代法则在特定场景下（如需要避免递归栈溢出）更具优势。

关键点解析 ​

  1. 后序遍历特性：递归法本质上是后序遍历的应用，先处理子树再处理当前节点
  2. 短路优化：当找到目标节点时，可以提前终止不必要的搜索
  3. 边界处理：巧妙利用空值传递信息，空值表示子树中无目标节点

常见误区 ​

  1. 误认为LCA必须是父节点（可能是祖父节点）
  2. 忘记处理节点自身是祖先的情况
  3. 混淆节点值和节点引用（Java中要比较对象地址）

实际应用 ​

  1. Git版本控制中的最近共同提交
  2. 社交网络中的共同联系人查找
  3. 生物信息学中的进化树分析
  4. 编译器中的符号解析

进阶思考 ​

  1. 如果树节点包含父指针，如何优化算法？
  2. 如何处理多个目标节点的LCA问题？
  3. 当树结构动态变化时，如何高效维护LCA信息？
  4. 在N叉树中如何寻找LCA？

总结 ​

LCA问题教会我们：

  1. 递归思维在树结构问题中的强大威力
  2. 通过分治策略将复杂问题拆解为子问题
  3. 不同数据结构组合带来的性能优化空间
  4. 算法设计中对边界条件的敏感性

无论是递归法还是迭代法，其核心都在于理解树结构的遍历特性。就像在家族中寻找共同祖先一样，算法本质上是在建立节点间的联系网络。

欢迎关注我的公众号【忍者算法】，回复【二叉树】获取精心整理的二叉树专题刷题手册。包含：

  1. 高频面试题分类解析
  2. 递归与非递归模板代码
  3. 经典题目变形题解
  4. 大厂真题实战演练

让我们一起在算法的世界里修炼忍者之道！🗡️