題目

  • 題目連結
  • 目標函式 : lowestCommonAncestor(root, p, q)
    • Input : root: TreeNode、p: TreeNode、q: TreeNode
    • Output : TreeNode

解題概念

  • 題意 : 給予一 Binary Search Tree root，找出給定兩節點 p 和 q 的 Lowest Common Ancestor (LCA)
  • Lowest Common Ancestor (LCA) 之定義 : Definition of LCA on Wikipedia

我的寫法

  • 想法 : 由於在 BST 中，一節點的 val 必定會大於其左子點的 val，同時小於其右子點的 val
  • 因此，只需從 root 使用 Top-down 的方式去搜尋即可，判斷條件如下 :
    • Case 1 : 若 p.val 與 q.val 皆小於 root.val → 則往左子樹下移 (root = root.left)
    • Case 2 : 若 p.val 與 q.val 皆大於 root.val → 則往右子樹下移 (root = root.right)
    • Case 3 : 若為剩餘狀況 → 則代表找到 LCA，回傳 root 即可
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    def lowestCommonAncestor(self, root, p, q):
        
        while root:
            if root.val > p.val and root.val > q.val:
                root = root.left
            elif root.val < p.val and root.val < q.val:
                root = root.right
            else:
                return root
        return root
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(\log(n))}$
    • Runtime: 56 ms (faster than 81.62%)
    • Memory Usage: 21.3 MB (more than 84.10%)

解答 or 其他優秀寫法

  • 想法 : 想法類似，但在細節處寫得更好
    1. 把數值比較的部分修改，以避免 val 出現 INT_MAX，進而導致 Overflow
      • 改使用 (root.val - p.val) * (root.val - q.val) > 0 去判斷是否為上述之 Case 1 與 Case 2
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    def lowestCommonAncestor(self, root, p, q):

        while (root.val - p.val) * (root.val - q.val) > 0: # 若符合 Case 1/2 的條件

            # 看 p 與 q 同時位於 root 的左子樹 or 右子樹
            root = root.left if p.val < root.val else root.right

        return root
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(\log(n))}$
    • Runtime: 57 ms (faster than 78.24%)
    • Memory Usage: 21.4 MB (more than 54.74%)