236-Lowest-Common-Ancestor-of-a-Binary-Tree.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    res = None

    def lowestCommonAncestor(
        self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
    ) -> "TreeNode":
        if not root or not p or not q:
            return None

        def search(root, p, q):
            if not root:
                return False
            mid = left = right = False
            if root.val == p.val or root.val == q.val:
                mid = True

            left = search(root.left, p, q)
            right = search(root.right, p, q)
            if mid:
                if left or right:
                    self.res = root
            elif left and right:
                self.res = root
            return mid or left or right

        search(root, p, q)
        return self.res