1 題目描述

給一個二元樹，找到兩個節點的最低共同祖先。（祖先可以是自己）

2 解法

2.1 我的解法

看到這題的時候我腦子裡面出現兩種情況：

如果兩個節點在同一個子樹下（p是q的子節點或是q是p的子節點），那祖先會是p或是q。
如果兩個節點在不同的子樹下（p和q分別在左右子樹下），那祖先會是把他們倆分開時的root。

情境1: p 是 q 的祖先或是 q 是 p 的祖先

情境2: p 和 q 在不同的子樹下

因此我們可以針對這兩種情況來寫遞歸。

情境1
我們可以建立一個function檢查兩個點是否在同一個子樹下，如果是的話，回傳p或是q。

def check_same_subtree(parent, child):
    if parent is None:
        return False
    if parent == child:
        return True
    return check_same_subtree(parent.left, child) or check_same_subtree(parent.right, child)

所以主程式可以這樣寫：

先檢查 p 是否為 q 的祖先（在同一個樹下），如果是就回傳 p
再檢查 q 是否為 p 的祖先（在同一個樹下），如果是就回傳 q

def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    if check_same_subtree(p, q):
        return p
    if check_same_subtree(q, p):
        return q

情境2
接下來我們開始處理情境2，也就是 p 和 q 在不同的子樹下。他的特點是在，我們一但同時在當前的root的left subtree與right subtree找到p 或是 q，就回傳當前的root。否則若只有一邊有，但是另一邊的subtree還沒有，那就代表還不夠高，繼續往上找。

從上圖可以看到，

class Solution:
    ans = None

    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if check_same_subtree(p, q):
            return p
        elif check_same_subtree(q, p):
            return q

        
    def find_parent(root):
        if root is None:
            return False
        if root == p or root == q: 
            return True
        
        left = find_parent(root.left)
        right = find_parent(root.right)

        # 如果左右子樹都有找到，代表當前的root就是答案
        if left and right: 
            self.ans = root 
        # 如果左右子樹有一個找到，代表還不夠高，繼續往上找
        elif left or right: 
            return True
        # 如果左右子樹都沒有找到，回傳False
        else: 
            return False 

    def check_same_subtree(parent, child):
        if parent is None:
            return False
        if parent == child:
            return True
        return check_same_subtree(parent.left, child) or check_same_subtree(parent.right, child)

最後結果就是


class Solution:
    ans = None

    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if check_same_subtree(p, q):
            return p
        elif check_same_subtree(q, p):
            return q
        else: 
            self.find_parent(root)
        return self.ans 

        
    def find_parent(root):
        if root is None:
            return False
        if root == p or root == q: 
            return True
        
        left = find_parent(root.left)
        right = find_parent(root.right)

        # 如果左右子樹都有找到，代表當前的root就是答案
        if left and right: 
            self.ans = root 
        # 如果左右子樹有一個找到，代表還不夠高，繼續往上找
        elif left or right: 
            return True
        # 如果左右子樹都沒有找到，回傳False
        else: 
            return False

2.2 更好的解法

在上面你會發現一個精神：

我們會檢查當前root的left subtree和right subtree是否有找到p或是q，如果有找到，就回傳當前的root。
如果只有一邊有找到，另一邊沒有，但還是回傳True
如果兩邊都沒找到，回傳False

那我們是否可以改變一下觀念，把Ture, False的概念換成回傳 True = p 或是 q 以及 False = None，這樣我們就可以把情境1和情境2合併在一起了。

具體來說是怎麼把情境1和2合併在一起呢？

情境1: 如果發現一邊是None，那我們就回傳另一邊
- 如果另一邊有值就會回傳最早碰到的節點（p或是q）那就是祖先。
- 如果另一邊沒有值，代表兩邊都沒有找到，就回傳None（但題目有說明p跟q一定會在樹裡面，所以這個情況不會發生）
情境2: 如果發現兩邊都有值，就代表我們找到 p 跟 q 節點了，但是因為他們在不同的子樹下，所以當前的root就是祖先。

class Solution: 
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        # 回傳 Ture 或是 False 概念 只是都是 root 
        if root is None or root == p or root == q:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        
        # 情境2 兩邊都有值，代表找到 p 跟 q，但是在不同的子樹下 回傳當前的root
        if left and right: 
            return root
        # 情境1 一邊有值，另一邊沒有值，回傳有值的那一邊
        if left or right: 
            return left or right