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

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

解法一：递归

观察规律，可以发现，如果满足 p.Val <= 当前节点.Val <= q.Val，那么说明该节点就是 p 和 q 的最近公共祖先，返回当前节点的地址。如果不符合，就根据 p 和 q 的值判断去左子树找还是去右子树找。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if p.val > q.val:    #保证p小于等于q
            p, q = q, p
        if not root or p.val <= root.val and root.val <= q.val:
            return root
        elif q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        else:
            return self.lowestCommonAncestor(root.right, p, q)