第二十五天 Lowest Common Ancestor of

每天刷两天，然后睡觉也踏实点，继续相信坚持的力量 不间断呢

求二叉搜索树的最近公共祖先

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

只要是涉及到二叉树的，就一定离不开递归，哈哈

这道题就要先充分利用二叉搜索树的特点，左子树一定是小于根和右子树，右子树一定是大于根和左子树的

那么，当p和q的值，较小的那个，都比"根"大，那么他们的最近公共祖先一定是在右子树
同理，当p和q的值，较大的那个，都比"根"小，那么他们的最近公共祖先一定是在左子树
如果他们是分布在根的两边，那么这个"根"就是最近公共祖先咯

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

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if root == None and p == None and q == None:
            return None
        if max(p.val,q.val) < root.val:
            return self.lowestCommonAncestor(root.left,p,q)
        elif min(p.val,q.val) > root.val:
            return self.lowestCommonAncestor(root.right,p,q)
        else:
            return root