"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        this.val = val
        this.left, this.right = None, None
"""


class Solution:
    """
    @param: root: The root of the binary tree.
    @param: A: A TreeNode
    @param: B: A TreeNode
    @return: Return the LCA of the two nodes.
    """
    def lowestCommonAncestor3(self, root, A, B):
        # write your code here
        self.found_A = False
        self.found_B = False

        ans = self.lca(root, A, B)
        return ans if (self.found_A and self.found_B) else None

    def lca(self, root, A, B):
        if not root:
            return None

        # divide
        found_left = self.lca(root.left, A, B) # keep traverse
        found_right = self.lca(root.right, A, B) # keep traverse

        if root == A: 
            self.found_A = True
        if root == B:
            self.found_B = True

        # conquer
        if found_left is not None and found_right is not None:
            return root
        elif root in (A, B): # found root in A or B
            return root
        elif found_left:
            return found_left
        elif found_right:
            return found_right
        else:
            return None