Excalidraw一键复用组件，大幅提升重复绘图效率
2025/12/22 2:45:19
🌳二叉树的“家谱学”：为什么最近公共祖先是最优解？
大家好，我是 Echo_Wish，一个天天跟数据结构泡在一起、看到指针比看到工资都兴奋的算法老哥。
今天咱不谈 AI 不谈大模型，也不整区块链，回归一下算法最质朴的浪漫 ——二叉树的最近公共祖先（Lowest Common Ancestor of a Binary Tree，简称 LCA）。
为什么我说它是算法的浪漫？因为 LCA 解决的是人类从古至今最执着的问题之一：
“咱俩到底最近的共同祖宗是谁？”
比如你和你同事吵架了，他告诉你：“别吵，你尊称我是你爷爷。”
你当然不服：
“你连我四世同堂都算不上！”
这时候要是树结构一跑，你真能算出来。
🧠 LCA 到底解决什么问题？
一句话概括：
在二叉树里，找到 p 和 q 这两个节点的最近公共祖先。
意味着：
- A、B 俩节点往上回溯
- 找到第一个交汇点
- 这个点是它们最近的共同父辈
不是任意公共祖先，是最近那个。
举个图更直观：
3 / \ 5 1 / \ / \ 6 2 0 8