最近公共祖先

最近公共祖先到底是什么

给定二叉树中的两个节点 p 和 q，最近公共祖先（LCA）是同时罩住两者、且层级最深的那个节点。有一个容易忽略的定义细节：节点可以是它自己的祖先——如果 p 本身就在 q 的上方，那 p 自己就是答案。这个细节直接决定了递归里「碰到 p 或 q 就立刻返回」这一步是安全的。

为什么不先求两条路径再比对

最直觉的做法是分别找出根到 p、根到 q 的两条路径，再从头对比，最后一个相同的节点就是 LCA。这个思路完全正确，但要遍历两趟、还要额外存两条路径。它的价值在于点破了问题的本质：LCA 就是两条根到目标路径的分岔点。递归解法的妙处，是把「找路径」和「比路径」压进同一趟遍历里完成。

递归函数的返回值到底代表什么

递归函数的语义是：在当前子树里搜索 p 和 q，返回找到的东西。结果只有三种：子树里一个目标都没有，返回空；只找到 p 和 q 中的一个，就把那个节点往上传；两个都在这棵子树里，返回它们的 LCA。递归时碰到空或者碰到 p、q 本身就直接返回自己——即使另一个目标还藏在它下面也没关系，因为那种情况当前节点本来就是两者的公共祖先，返回自己恰好正确。

为什么左右都非空时当前节点就是答案

按后序的方式先问左子树、再问右子树，两边的答案都拿到后再裁决。若左右各返回一个非空节点，说明 p、q 分居当前节点的两侧，这里是两条向上路径第一次汇合的位置；任何更深的节点都不可能同时罩住分居两边的目标，所以当前节点就是最近的那个公共祖先。若只有一边非空，说明目标（或已经在下面算出的 LCA）全在那一边，原样上传即可；两边都空就传空。

这也解释了为什么必须是后序遍历：父亲的裁决完全依赖左右孩子的搜索结果，孩子不先算完，父亲无从判断。

复杂度多少，还有哪些追问

每个节点恰好被访问一次，时间 O(n)；递归栈深等于树高 h，平衡树是 O(log n)，最坏退化成链是 O(n)。

两个常见追问：若不保证 p、q 都在树里，要在后序里额外用两个布尔量确认两者真的都被找到，否则交汇点不算数；若树是二叉搜索树（LeetCode 235），可以利用有序性从根往下走——p、q 都比当前小就走左，都比当前大就走右，第一次分居两侧的节点即 LCA，只需 O(h) 且不必搜索两边。