Description
給定一棵二元搜尋樹 (BST) 和兩個節點 p、q，找到它們的最低共同祖先 (LCA)。LCA 定義為同時是 p 和 q 祖先的最深節點。
Example:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6
Intuition#
利用 BST 性質：若 p 和 q 分別在當前節點的兩側，當前節點就是 LCA。
- BST 中左子樹所有值 < 根 < 右子樹所有值
- 若 p、q 都小於根，LCA 在左子樹；都大於根，LCA 在右子樹；否則當前節點就是 LCA
Approaches#
1: Recursive#
- 概念: 根據 BST 性質遞迴搜尋
- 時間複雜度:
O(h)，h 為樹高 - 空間複雜度:
O(h)，遞迴堆疊
class Solution {
fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
if (root == null || p == null || q == null) return null
if (p.`val` < root.`val` && q.`val` < root.`val`) {
return lowestCommonAncestor(root.left, p, q)
}
if (p.`val` > root.`val` && q.`val` > root.`val`) {
return lowestCommonAncestor(root.right, p, q)
}
return root
}
}⭐ 2: Iterative#
- 概念: 同樣利用 BST 性質，但用迴圈代替遞迴，節省堆疊空間
- 時間複雜度:
O(h) - 空間複雜度:
O(1)
class Solution {
fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
var current = root
while (current != null) {
if (p!!.`val` < current.`val` && q!!.`val` < current.`val`) {
current = current.left
} else if (p.`val` > current.`val` && q!!.`val` > current.`val`) {
current = current.right
} else {
return current
}
}
return null
}
}🔑 Takeaways#
- Pattern: 利用 BST 有序性質做二分搜尋式的遍歷
- 關鍵技巧: BST 的 LCA 不需要回溯，只需要沿著樹向下走，比一般二元樹的 LCA 簡單得多