題目解釋
給定二元搜尋樹 (BST),找出 BST 中兩個給定節點的 最低共同祖先 (Lowest Common Ancestor, LCA) 節點。
LCA 的定義:
兩個節點 p
和 q
之間的最低共同祖先,
也就是在 BST 中,p 和 q 都是那個 node 的 descendent 的最低點,
此外單一個 node 也是其自身的 descendent。
範例
- 輸入:
root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8
- 輸出:
6
節點 2
和 8
的 LCA 是 6
。
最佳解法
假設我們有一個只有三個 node 的 BST,
我們可以善用 BST 的特性來判定下面的 node 會在哪裡:
- if node 值 < root 值 => node 一定會在 root 的 左邊
- if node 值 > root 值 => node 一定會在 root 的 右邊
好,現在如果我們還想知道另一個 node 在哪裡,
我們就需要知道它跟第一個 node 的關係來判定!
- if root 在 node1 跟 node2 的中間,那 root 就是它們倆的 LCA
- if node1 跟 node2 的值 都比 root 小,代表要再往 左 找
- if node1 跟 node2 的值 都比 root 大,代表要再往 右 找
如果懂了上方的邏輯,恭喜你,你也就會寫這題啦 ~
程式碼
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
curr = root
while curr:
if (p.val < curr.val) and (q.val < curr.val):
curr = curr.left
elif (p.val > curr.val) and (q.val > curr.val):
curr = curr.right
else:
return curr
時間複雜度
O(h)
,h 是 root
的高度,長的平均的話最好情況是 O(log n)
。
空間複雜度
O(1)
,沒有多存東西,
結語
也算高頻題,務必好好把握❗
Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)
- [推薦工具] 讓程式碼截圖變的美美的吧!VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
- [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
- [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26