42.YA

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def dfs(root):
            if root in (None, p, q):
                return root

            left = dfs(root.left)
            right = dfs(root.right)

            if left and right:
                return root
            elif left:
                return left
            elif right:
                return right
            else:
                return None

        return dfs(root)