題目

解題概念

  • 此題簡單來說，就是給定兩個節點 p 與 q，找出他們的 Lowest Common Ancestor (LCA；最低共同祖先)
  • 此題共有兩種解法，一種是遞迴的方式，另一種是用迭代與 DFS 的方式，而我此次採用第一種方式
  • 實際執行上，遞迴的判斷條件有兩種 :
    1. 若 p 與 q 分別在 root 的兩側，則他們的 LCA 就是 root
    2. 若 p 與 q 在 root 的同一側，則他們的 LCA 是這兩個節點中最低的節點
  • 而遞迴的終止條件有兩種 :
    1. root 為 None : 回傳 root 即可
    2. root 剛好是 p 或 q : 回傳 root

實際寫Code

  • 目標函式 : lowestCommonAncestor(root, p, q)
    • 節點格式 : 
      1
      2
      3
      4
      5
      class TreeNode(object):
          def __init__(self, val=0, left=None, right=None):
              self.val = val
              self.left = left
              self.right = right
    • Input : root: TreeNode、p: TreeNode、q: TreeNode
    • Output : TreeNode
  • 主要遞迴 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    # 遞迴的兩種終止條件
    if root == None or root == p or root == q :
            return root

    # 獲得左子樹的 LCA
    left = self.lowestCommonAncestor(root.left, p, q)

    # 獲得右子樹的 LCA
    right = self.lowestCommonAncestor(root.right, p, q)

    # 遞迴判斷條件 Case 1 : p 與 q 在不同側
    if left and right :
        return root

    # 遞迴判斷條件 Case 2 : p 與 q 在同側        
    return left if left else right

參考資料

  1. Wikipedia - Lowest Common Ancestor（一）