type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为
对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,
满足: x 是 p、q 的祖先,且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。
示例 1:

示例 2:

示例 3:
解法一:Bottom-Up DFS
利用“从下往上冒泡”的特性:如果在某个子树里能“看到”
p 或 q,就把“看到的那个节点”往上返;当某个节点左右子树都能看到时,说明
p、q 分处两边,当前节点就是 LCA。如果当前节点本身就是
p 或 q,那它也可能是答案(“祖先可以是自己”)。使用递归实现,递归返回值的含义是:在这棵子树里“看到”的候选(可能是
p / q / LCA / None)。汇总左右返回:两边都非空 → 当前即 LCA;只有一边非空 → 这一边的候选继续向上;都空 → 返回 None。
复杂度
- 时间:
O(N)(N 为节点数,最坏遍历一次整树)
- 空间:
O(H)(H 为树高;最坏退化链为O(N))
解法二:迭代 — 父指针哈希 + 祖先集合
用栈/队列做DFS/BFS,构建 parent哈希表,然后:
- 从
p一路往上,把祖先全放进一个集合;
- 再从
q一路往上爬,第一个落在集合里的节点就是 LCA。
复杂度
- 时间:
O(N)建表 +O(H)回溯
- 空间:
O(N)存 parent 与集合
解法三:DFS找根到两个节点的路径
拿到“根→节点”的完整路径,那 LCA 自然就是两条路径最后一个相同的节点:
- 写一个找路径的 DFS:
path(root, target);
- 拿到
path_p、path_q,从头一起走,走到分叉前的最后一个即 LCA。
复杂度
- 时间:最坏
O(N)(找两次路径)
- 空间:
O(H)(递归栈 + 路径)
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-236-二叉树的最近公共祖先
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
上一篇
[Leetcode 208] 实现 Trie
下一篇
[Leetcode 239] 滑动窗口最大值
