问题描述：

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree:  root = [6,2,8,0,4,7,9,null,null,3,5]

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8

Output: 6

Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4

Output: 2

Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Note:

• All of the nodes' values will be unique.
• p and q are different and both values will exist in the BST.

思路：

这个需要用到二叉搜索树的性质，即左子树的值小于根的值，右子树的值大于根的值。

基于以上性质，根据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: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

         if root == None:

             return

         if (p.val <= root.val and q.val >= root.val) or (p.val >= root.val and q.val <= root.val):

             return root

         elif (p.val < root.val and q.val < root.val):

             return self.lowestCommonAncestor( root.left, p, q)

         elif (p.val > root.val and q.val > root.val):

             return self.lowestCommonAncestor( root.right, p, q)