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

若 root 是 p, q 的 最近公共祖先 ，则只可能为以下情况之一：

1. p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
2. p=root ，且 q 在 root 的左或右子树中；
3. q=root ，且 p 在 root 的左或右子树中；

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    # 二叉树，
    if not root:
        return root
    if root==q or root==p:
        return root
    l=lowestCommonAncestor(root.left,p,q)
    r=lowestCommonAncestor(root.right,p,q)
    if not l:
        return r
    if not r:
        return l
    return root

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    # 二叉搜索树
    if p.val<root.val and q.val<root.val:
        return lowestCommonAncestor(root.left,p,q)
    elif p.val>root.val and q.val>root.val:
        return lowestCommonAncestor(root.right,p,q)
    #只在(p.val-root.val)*(q.val-root.val)<0 即两者异号的时候返回root，同号归边。
    return root