2026/7/6大约 5 分钟
LeetCode 236. 二叉树的最近公共祖先
题目核心
给定一棵普通二叉树的根节点 root，以及两个节点 p 和 q，返回它们的最近公共祖先。
最近公共祖先指的是：在树中同时拥有 p 和 q 作为后代的最深节点。一个节点也可以是它自己的后代，所以如果 p 是 q 的祖先，答案就是 p。
解题思考过程
第一步：理解问题
最近公共祖先（LCA）是树中两个节点的公共祖先中最深的那个。
示例：
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
p=5, q=1: LCA是3
p=5, q=4: LCA是5（因为4是5的后代）第二步：暴力解法（存储路径）
最直接的思路：
- 找到从根到p的路径
- 找到从根到q的路径
- 比较两条路径，找到最后一个公共节点
路径3->5->2->4 和路径3->5->6
公共节点是3和5，最后一个是5，所以LCA是5时间复杂度：O(n)
空间复杂度：O(n) - 需要存储两条路径第三步：思考如何优化空间
能不能在一次遍历中找到LCA？
想到后序遍历：先处理左右子树，再处理当前节点。
递归返回值的含义：
- 返回null：子树中没有p和q
- 返回p：子树中有p
- 返回q：子树中有q
- 返回LCA：子树中找到了p和q的最近公共祖先第四步：后序遍历的逻辑
后序遍历(root):
if root == null || root == p || root == q:
return root
left = 后序遍历(root.left)
right = 后序遍历(root.right)
if left != null && right != null:
// p和q分别在左右子树，当前节点就是LCA
return root
elif left != null:
// p和q都在左子树
return left
else:
// p和q都在右子树
return right第五步：验证后序遍历
以 p=5, q=1 为例：
后序遍历(3):
后序遍历(5):
后序遍历(6): 返回6（不是p或q，返回null？不，6不是p或q，返回null）
后序遍历(2):
后序遍历(7): 返回null
后序遍历(4): 返回null
返回null
5 == p，返回5
后序遍历(1):
后序遍历(0): 返回null
后序遍历(8): 返回null
1 == q，返回1
left=5, right=1，都不为null
返回3（LCA）✓以 p=5, q=4 为例：
后序遍历(3):
后序遍历(5):
后序遍历(6): 返回null
后序遍历(2):
后序遍历(7): 返回null
后序遍历(4): 4 == q，返回4
返回4
5 == p，返回5（因为5本身就是p，直接返回）
后序遍历(1): 返回null
left=5, right=null
返回5（LCA）✓第六步：为什么后序遍历能找到LCA
后序遍历的特点是先处理子节点，再处理父节点。
当我们在某个节点发现：
- 左子树返回了p或q
- 右子树返回了另一个
说明p和q分别在左右子树，当前节点就是它们的最近公共祖先。
时间复杂度：O(n)
空间复杂度：O(h) - 递归栈深度当前解法：后序遍历递归
当前代码使用的是后序遍历思想：
function lowestCommonAncestor(
root: TreeNode | null,
p: TreeNode | null,
q: TreeNode | null,
): TreeNode | null {
if (root == null || root == p || root == q) {
return root;
}
let left = lowestCommonAncestor(root.left, p, q);
let right = lowestCommonAncestor(root.right, p, q);
if (left != null && right == null) {
return left;
}
if (left == null && right != null) {
return right;
}
if (left != null && right != null) {
return root;
}
return null;
}算法思想
递归函数的返回值含义非常关键：
在以 root 为根的子树中，是否找到了 p 或 q，或者已经找到了最近公共祖先。具体来说：
- 如果当前节点是
null，说明这条路径没有找到目标节点，返回null。 - 如果当前节点等于
p或q，说明找到了其中一个目标节点，返回当前节点。 - 否则递归搜索左子树和右子树。
因为要先知道左右子树的搜索结果，再决定当前节点是不是最近公共祖先，所以这是后序遍历：
左子树 -> 右子树 -> 当前节点四种返回情况
递归得到 left 和 right 后，有四种情况。
1. 左右都为空
left == null && right == null说明当前子树里没有找到 p 或 q，返回 null。
2. 左不为空，右为空
left != null && right == null说明目标节点在左子树中，返回 left。
这里的 left 可能是 p、q，也可能是已经找到的最近公共祖先。
3. 左为空，右不为空
left == null && right != null说明目标节点在右子树中，返回 right。
同样，right 可能是 p、q，也可能是已经找到的最近公共祖先。
4. 左右都不为空
left != null && right != null说明 p 和 q 分别出现在当前节点的左右两侧，因此当前节点就是它们的最近公共祖先，返回 root。
为什么返回当前节点就是最近公共祖先
递归是从下往上返回的。
当某个节点第一次发现：
左子树找到了一个目标节点，右子树也找到了一个目标节点这个节点就是离 p 和 q 最近的分叉点。
因为更深的节点只会出现在左子树或右子树的一边，不可能同时覆盖两个目标节点。所以第一次满足左右都不为空的节点，就是最近公共祖先。
复杂度
- 时间复杂度：
O(n) - 空间复杂度：
O(h)
其中 n 是二叉树节点数量，h 是树的高度。空间复杂度来自递归调用栈。
在最坏情况下，树退化成链表，h = n；在平衡二叉树中，h = log n。