[Leetcode 236] 二叉树的最近公共祖先

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

解法一:Bottom-Up DFS

利用“从下往上冒泡”的特性:如果在某个子树里能“看到” pq,就把“看到的那个节点”往上返;
当某个节点左右子树能看到时,说明 pq 分处两边,当前节点就是 LCA
如果当前节点本身就是 pq,那它也可能是答案(“祖先可以是自己”)。
使用递归实现,递归返回值的含义是:在这棵子树里“看到”的候选(可能是 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_ppath_q,从头一起走,走到分叉前的最后一个即 LCA。
复杂度
  • 时间:最坏 O(N)(找两次路径)
  • 空间:O(H)(递归栈 + 路径)
Buy Me a Coffee
上一篇
[Leetcode 208] 实现 Trie
下一篇
[Leetcode 239] 滑动窗口最大值