# **Leetcode筆記(Lowest Common Ancestor of a Binary Tree)**

:::info
:information_source: 題目 : Lowest Common Ancestor of a Binary Tree, 類型 : binary tree , 等級 : medium
日期 : 2023/05/23，2024/08/24，2024/10/05
:::

### 嘗試

用樹枝去傳node，如果只有單邊有node，那就傳單邊node，如果雙邊都有，那就傳它們的parent node

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        
        def helper(node, p, q):
            if not node:
                return None
            if node == p or node == q:
                return node
            
            left = helper(node.left, p, q)
            right = helper(node.right, p, q)

            if left and right:
                return node
            if left:
                return left
            if right:
                return right

        return helper(root, p, q)

2024/08/24

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        
        def helper(node, p, q):
            if not node:
                return None
            
            if node == p or node == q:
                return node
            
            left = helper(node.left, p, q)
            right = helper(node.right, p, q)

            if left and right:
                return node
            
            if left:
                return left
            
            if right:
                return right
        
        return helper(root, p, q)

2024/10/05

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        
        def traverse(node):
            if not node:
                return None
            if node == p or node == q:
                return node

            l = traverse(node.left)
            r = traverse(node.right)

            if l and r:
                return node
            elif l:
                return l
            elif r:
                return r
            else:
                return None
        
        return traverse(root)

---
### **優化**
lowest common ancestor (LCA) : 最小的共同祖先

在最壞情況下，需要遍歷整個二叉樹來尋找最低共同祖先，時間複雜度為 O(n)

遞迴過程中，除了樹本身的空間佔用外，額外使用的空間是遞迴調用棧的空間。在最壞情況下，遞迴的深度可以達到樹的高度，而樹的高度最壞情況下為 O(n)（完全不平衡的樹），空間複雜度為 O(n)。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # return遞迴的東西 可以想成是在樹枝上傳遞
        # 從最底部開始操作
        # return回"上面"的樹枝
        # 遞迴是會從這個函式的"最上層開始"往下進入if條件式
        # 有任一個成立 即會回傳

        def helper(node, p, q):
            # 直接針對node的部分
            if not node:
                return None
            if node == p or node == q:
                return node

            # 會在這邊判斷node的左右
            left = helper(node.left, p, q)
            right = helper(node.right, p, q)

            # 然後選擇回傳(return)哪些東西給自己node的上方樹枝
            if left and right:
                return node
            if left:
                return left
            if right:
                return right
        
        return helper(root, p, q)

---

**:warning: 錯誤語法**
:::warning

:::

**:thumbsup:學習**
:::success

:::

**思路**
從下面往上看，當左邊有東西，右邊有東西，返回那個節點的數值
當左(右)邊有東西，右(左)邊沒有東西，則返回有東西那一邊的數值
兩邊有東西就返回節點5
直接返回5，因為一邊有東西一邊沒東西

**講解連結**
https://www.youtube.com/watch?v=T-PGz0jnAHA&ab_channel=%E5%AE%B0%E7%9B%B8%E5%B0%8F%E7%94%98%E7%BD%97
Provided by. 宰相小甘罗

###### tags: `binary tree` `medium` `leetcode`