二叉树的“家谱学”：为什么最近公共祖先是最优解？

🌳二叉树的“家谱学”：为什么最近公共祖先是最优解？

大家好，我是 Echo_Wish，一个天天跟数据结构泡在一起、看到指针比看到工资都兴奋的算法老哥。

今天咱不谈 AI 不谈大模型，也不整区块链，回归一下算法最质朴的浪漫 ——二叉树的最近公共祖先（Lowest Common Ancestor of a Binary Tree，简称 LCA）。

为什么我说它是算法的浪漫？因为 LCA 解决的是人类从古至今最执着的问题之一：

“咱俩到底最近的共同祖宗是谁？”

比如你和你同事吵架了，他告诉你：“别吵，你尊称我是你爷爷。”
你当然不服：
“你连我四世同堂都算不上！”
这时候要是树结构一跑，你真能算出来。

🧠 LCA 到底解决什么问题？

一句话概括：

在二叉树里，找到 p 和 q 这两个节点的最近公共祖先。

意味着：

• A、B 俩节点往上回溯
• 找到第一个交汇点
• 这个点是它们最近的共同父辈

不是任意公共祖先，是最近那个。

举个图更直观：

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