image.png
如果树是查找树，可以优化
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
a1,a2 = root.val-p.val, root.val-q.val
if a1*a2<=0: return root
elif a1<0: return self.lowestCommonAncestor(root.right, p, q)
else: return self.lowestCommonAncestor(root.left, p, q)
