0%
Loading ...

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

image 1723795952890

題目解釋

給定二元搜尋樹 (BST),找出 BST 中兩個給定節點的 最低共同祖先 (Lowest Common Ancestor, LCA) 節點。

LCA 的定義:
兩個節點 pq 之間的最低共同祖先,
也就是在 BST 中,p 和 q 都是那個 node 的 descendent 的最低點,
此外單一個 node 也是其自身的 descendent。

範例

file

  • 輸入: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8
  • 輸出: 6

節點 28 的 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),沒有多存東西,

結語

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

數據女巫 𝔻.𝕡𝕪𝕤 🔮

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

The reCAPTCHA verification period has expired. Please reload the page.