題目出處

235. Lowest Common Ancestor of a Binary Search Tree

難度

easy

個人範例程式碼

# 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 p <mark> root or q </mark> root:
            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: # two side found
            return root
        elif found_left: # found left
            return found_left
        elif found_right: # found right
            return found_right
        else: # not found
            return None

算法說明

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

https://wongwongnotes-github-io.pages.dev/python/lintcode-python-474/

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