LeetCode 236 - 二叉树的最近公共祖先

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

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:  # 左右子树都找到了祖先，则根节点是最近公共祖先
            return root
        elif left:  # 左子树找到了祖先
            return left
        else:  # 右子树找到了祖先，或者左右子树都没有找到
            return right  # 注意：这里需要返回 right，即使 right 为 None