# Leetcode 236. Lowest Common Aesntor of Binary Tree

## 題解

<iframe width="560" height="315" src="https://www.youtube.com/embed/KobQcxdaZKY?si=XcGj0Eiau6q-svtv" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>
<br></br>

# 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':
        # Time complexity: O(n)
        # Space complexity: O(n) -- stack call
        if root is None: # base case
            return None
        # Post order traversal
        left = self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)
        if (left and right) or (root in [p,q]): # if root in [p,q] , meats the common anestor is it self or in other sub tree
            return root
        else: # missing left or right , just return one of them exists
            return left or right