Given a binary tree, find the lowest common ancestor LCA of two given nodes in the tree. According to the definition of LCA on Wikipedia: The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants where we allow a node to be a descendant of itself. 3                5          1                      6      2       0       8    7   4 For example, the lowest common ancestor LCA of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition. :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode
def lca(root, p, q):
    """
    :type root: TreeNode
    :type p: TreeNode
    :type q: TreeNode
    :rtype: TreeNode
    """
    if root is None or root is p or root is q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left is not None and right is not None:
        return root
    return left if left else right
