Lowest Common Ancestor of a Binary Tree

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

# 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':
        if root is None or root.val == p.val or root.val == q.val:
            return root
        # leap of faith: left and right maybe the answer, so we need examine another step
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        # accomplish the leap of faith for father 
        if left is not None and right is not None:
            # left and right both find -> this root is lowestCommentAncestor
            # because any other node, the father or son of root, must have one of left/right is None
            return root

        # None or None -> None
        # None or p/q -> p/q
        # None or lowestCommentAncestor -> lowest
        if left is not None:
            return left
        if right is not None:
            return right
        return None