【Leetcode 筆記】235. Lowest Common Ancestor of a Binary Search Tree

題目解釋

給定二元搜尋樹 (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)，沒有多存東西，

結語

也算高頻題，務必好好把握❗

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

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