👋 大家好，欢迎来到我的技术博客！
💻 作为一名热爱 Java 与软件开发的程序员，我始终相信：清晰的逻辑 + 持续的积累 = 稳健的成长。
📚 在这里，我会分享学习笔记、实战经验与技术思考，力求用简单的方式讲清楚复杂的问题。
🎯 本文将围绕数据结构与算法这个话题展开，希望能为你带来一些启发或实用的参考。
🌱 无论你是刚入门的新手，还是正在进阶的开发者，希望你都能有所收获！

---

🤝 数据结构与算法：二叉树的最近公共祖先 —— 递归与哈希表两种思路

在二叉树的诸多问题中，寻找最近公共祖先（Lowest Common Ancestor, LCA） 是一个经典且富有挑战性的题目。它要求我们找到两个指定节点在树中的“交汇点”——即深度最大的、同时是这两个节点祖先的节点。

LCA 问题不仅逻辑精巧，而且在现实世界中有广泛的应用，例如在文件系统中定位共同目录、在社交网络中寻找最近的共同好友、在版本控制系统中比较分支的共同基点等。

解决 LCA 问题主要有两种思路：递归法 和 哈希表法。前者利用树的递归结构，代码优雅高效；后者通过预处理存储父节点信息，查询快速但需要额外空间。

本文将带你深入探索这两种方法。我们将通过 详尽的 Java 代码示例、生动的 emoji 图标、清晰的 Mermaid 图表 以及 权威的外部参考资料，全面剖析每种方法的原理、实现与优劣。无论你是准备面试的求职者，还是希望提升算法能力的开发者，这篇文章都将为你提供一份深入、实用的指南。

💡 提示：本文不设传统目录，而是以连贯的叙事方式，从问题定义出发，逐一实现并对比两种方法，最终让你对 LCA 问题了然于胸。

---

🌳 什么是最近公共祖先（LCA）？

给定一棵二叉树和两个节点 p 和 q，它们的最近公共祖先是满足以下条件的深度最大的节点：

1. 该节点是 p 的祖先。
2. 该节点是 q 的祖先。

🌱 示例树

• p = 5, q = 1 → LCA = 3
• p = 5, q = 4 → LCA = 5
• p = 6, q = 4 → LCA = 5

---

🔄 方法一：递归法（推荐）

递归法是解决 LCA 问题最优雅、最高效的方法。其核心思想是：如果当前节点是 p 或 q，或者 p 和 q 分别位于当前节点的左右子树中，那么当前节点就是 LCA。

💻 Java 代码实现

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class LCASolution {
    
    /**
     * 递归求解最近公共祖先
     * @param root 根节点
     * @param p 节点 p
     * @param q 节点 q
     * @return 最近公共祖先节点
     */
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 基础情况：空节点或找到 p/q
        if (root == null || root == p || root == q) {
            return root;
        }
        
        // 在左子树中查找
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 在右子树中查找
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        // 如果 left 和 right 都不为空，说明 p 和 q 分别在两侧，root 是 LCA
        if (left != null && right != null) {
            return root;
        }
        
        // 否则，LCA 在不为空的那一侧
        return left != null ? left : right;
    }
}

✅ 优点

• 时间复杂度 O(n)：每个节点最多访问一次。
• 空间复杂度 O(h)：h 为树的高度，递归栈的深度。
• 代码简洁：逻辑清晰，易于理解和记忆。
• 无需额外数据结构：不依赖哈希表等。

⚠️ 缺点

• 依赖递归：在极深的树上可能栈溢出。
• 单次查询：每次查询都需要遍历树。

---

🔄 方法二：哈希表法（预处理 + 查询）

哈希表法的思路是：先遍历整棵树，用哈希表记录每个节点的父节点。然后，从 p 开始，沿着父节点向上追溯，将路径上的所有节点存储在一个集合中。最后，从 q 开始向上追溯，第一个出现在集合中的节点就是 LCA。

💻 Java 代码实现

import java.util.*;

public class LCASolutionHashTable {
    
    private Map<TreeNode, TreeNode> parentMap; // 存储节点到父节点的映射
    private Set<TreeNode> ancestors; // 存储从 p 到根的路径
    
    public LCASolutionHashTable() {
        parentMap = new HashMap<>();
        ancestors = new HashSet<>();
    }
    
    /**
     * 预处理：填充父节点映射
     */
    private void dfs(TreeNode node, TreeNode parent) {
        if (node != null) {
            parentMap.put(node, parent);
            dfs(node.left, node);
            dfs(node.right, node);
        }
    }
    
    /**
     * 使用哈希表求解 LCA
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 步骤1: 预处理，建立父节点映射
        dfs(root, null);
        
        // 步骤2: 从 p 向上追溯，记录所有祖先
        TreeNode current = p;
        while (current != null) {
            ancestors.add(current);
            current = parentMap.get(current);
        }
        
        // 步骤3: 从 q 向上追溯，找到第一个共同祖先
        current = q;
        while (current != null) {
            if (ancestors.contains(current)) {
                return current;
            }
            current = parentMap.get(current);
        }
        
        return null; // 理论上不会到达这里
    }
}

✅ 优点

• 查询快速：预处理后，查询时间复杂度为 O(h)。
• 可多次查询：如果需要对同一棵树进行多次 LCA 查询，哈希表法更高效。
• 避免递归：查询过程是迭代的，无栈溢出风险。

⚠️ 缺点

• 空间开销大：需要 O(n) 的空间存储父节点映射和祖先集合。
• 预处理开销：首次查询需要 O(n) 时间进行预处理。
• 代码复杂：相比递归法，代码更长，逻辑更复杂。

---

📊 两种方法对比

特性	递归法	哈希表法
时间复杂度（单次查询）	O(n)	O(n) 预处理 + O(h) 查询
空间复杂度	O(h)	O(n)
代码简洁性	⭐⭐⭐⭐⭐	⭐⭐⭐
适合多次查询	❌	✅
栈溢出风险	可能	无（查询时）

---

🌐 相关阅读

• GeeksforGeeks: Lowest Common Ancestor in a Binary Tree —— LCA 问题的详细解析。
• Wikipedia: Lowest common ancestor —— LCA 的维基百科条目。

---

📈 总结

方法	适用场景
递归法	单次查询，代码简洁性优先，树高度适中
哈希表法	多次查询，查询性能要求高，内存充足

在大多数情况下，递归法是首选，因其简洁高效。而当需要对同一棵树进行大量 LCA 查询时，哈希表法的预处理优势将显现出来。

掌握这两种方法，不仅能解决 LCA 问题，更能加深对树的遍历、哈希表应用以及算法设计中“时间-空间权衡”的理解。

---

🙌 感谢你读到这里！
🔍 技术之路没有捷径，但每一次阅读、思考和实践，都在悄悄拉近你与目标的距离。
💡 如果本文对你有帮助，不妨 👍 点赞、📌 收藏、📤 分享 给更多需要的朋友！
💬 欢迎在评论区留下你的想法、疑问或建议，我会一一回复，我们一起交流、共同成长 🌿
🔔 关注我，不错过下一篇干货！我们下期再见！✨