leetcode原题链接：剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
# 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 not root:
return None
if root.val > p.val and root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)
if root.val < p.val and root.val < q.val:
return self.lowestCommonAncestor(root.right, p, q)
return root复杂度分析：
时间复杂度 ：
O
(
N
)
O(N)
O(N)，其中 N 为二叉树节点数；每循环一轮排除一层，二叉搜索树的层数最小为
log
N
\log N
logN （满二叉树），最大为 N（退化为链表）。
空间复杂度 ：
O
(
N
)
O(N)
O(N) ，最差情况下，即树退化为链表时，递归深度达到树的层数 N 。