給定一棵二元樹與其中兩個節點
p、q，找出它們的最低公共祖先（LCA）。LCA 定義為同時以p、q為後代、且深度最大的節點（一個節點也可以是自己的後代）。與 235（BST 版）不同，這裡沒有排序性質，不能靠值大小往左右走。
Example:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5（5 是 4 的祖先，自己也算後代）
Intuition
TIP
核心思路：後序遞迴。一個節點若「左子樹找到一個、右子樹找到一個」，它就是 LCA；若兩者都在同一側，LCA 在那一側。
- 對每個節點問：
p、q是否出現在我這棵子樹裡？ - 遞迴回傳「在這棵子樹中找到的目標節點（或 LCA）」
- 第一個左右各回傳非空的節點，就是答案——往上只會原封不動傳遞
Approaches
1. Find Two Paths then Compare — O(n) / O(n)
- Idea: DFS 找出 root → p 與 root → q 的路徑，再從頭比對到最後一個相同節點
- Time:
O(n)- 最多走訪全部節點 - Space:
O(n)- 兩條路徑與遞迴堆疊
class Solution {
fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
val pathP = ArrayList<TreeNode>()
val pathQ = ArrayList<TreeNode>()
findPath(root, p, pathP)
findPath(root, q, pathQ)
var lca: TreeNode? = null
var i = 0
while (i < pathP.size && i < pathQ.size && pathP[i] === pathQ[i]) {
lca = pathP[i]; i++
}
return lca
}
private fun findPath(node: TreeNode?, target: TreeNode?, path: ArrayList<TreeNode>): Boolean {
if (node == null) return false
path.add(node)
if (node === target) return true
if (findPath(node.left, target, path) || findPath(node.right, target, path)) return true
path.removeAt(path.size - 1)
return false
}
}⭐ 2. Single Postorder Recursion — O(n) / O(h)
- Idea: 命中
p或q就回傳該節點；某節點左右都回傳非空代表兩目標分屬兩側，自己即 LCA - Time:
O(n)- 每個節點訪問一次 - Space:
O(h)- 遞迴堆疊，h 為樹高
class Solution {
fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
if (root == null || root === p || root === q) return root
val left = lowestCommonAncestor(root.left, p, q)
val right = lowestCommonAncestor(root.right, p, q)
return when {
left != null && right != null -> root // p、q 分屬兩側 → 自己是 LCA
else -> left ?: right // 都在同一側，往上傳遞
}
}
}🔑 Takeaways
- Pattern: 樹形 DFS（後序），用「子樹是否含目標」的回傳值往上合成答案
- Key trick:
root === p || root === q時直接回傳本身（一個節點可為自己的後代）；左右皆非空 = LCA。對照 235 BST 版可用值大小 O(h) 直接走，本題沒有排序性質只能掃整棵