題目出處

236. Lowest Common Ancestor of a Binary Tree

難度

medium

個人範例程式碼

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        return self.lca(root, p, q)

    def lca(self, root, p, q):
        if not root:
            return None
        if root == p or root == q:
            return root

        # divide
        found_left = self.lca(root.left, p, q)
        found_right = self.lca(root.right, p, q)

        # conquer
        if found_left is not None and found_right is not None:
            return root
        elif found_left:
            return found_left
        elif found_right:
            return found_right
        else: # not found
            return None

算法說明

這已經是系列題目的第三題了，前面可參考

• 此系列題目的第一題，由於設計上多了 parent node，相對來說比較沒有考到 LCA 的經常考點：

【Lintcode】python – [474] Lowest Common Ancestor II 個人解法筆記

• 此系列題目的第二題，BST 與 BT 只多了比較好找數字，基本上有正確實作 LCA 其實也不用管數字排序：

【Leetcode】python – [235] Lowest Common Ancestor of a Binary Search Tree 個人解法筆記

LCA 的基本寫法，非常重要的題目。

拆成四路分析，左右返回是否有找到 A or B

討論 case 如下：

• 如果兩側各返回 found，表示一邊各找到一個，此 node 即為答案
• 如果只有 left/right 返回 found，表示已經在下層找到答案，正在往上回傳。
• 如果都沒有 found，表示目前往下還找不到，返回 None

而特殊的 case 為：

當 A 為 root，而 B 在此 root 之下，或相反的情況，
此時我們做的處理為返回 root，因為兩者的交集就是在 root 是兩者同時的 LCA。

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

Reference

• 474 · Lowest Common Ancestor II