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

本题解利用了二叉搜索树的性质来找到两个节点的最近公共祖先。在二叉搜索树中，对于任何一个节点，其左子树的所有节点值都小于该节点值，其右子树的所有节点值都大于该节点值。算法从根节点开始，比较两个节点值p和q与当前节点值的大小关系：如果p和q的值都大于当前节点值，则说明它们的公共祖先在当前节点的右侧子树中；如果p和q的值都小于当前节点值，则说明它们的公共祖先在当前节点的左侧子树中；如果p和q的值一个大于当前节点值，一个小于或等于当前节点值，那么当前节点就是它们的最近公共祖先。

时间复杂度: O(h)，其中h是树的高度。对于平衡的二叉搜索树，h约为log(n)。

空间复杂度: O(1)，因为算法仅使用有限的几个变量，而不依赖于输入大小。

# 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':
        while root:
            # 如果p和q都大于root的值，说明公共祖先在右子树
            if q.val > root.val and p.val > root.val:
                root = root.right
            # 如果p和q都小于root的值，说明公共祖先在左子树
            elif q.val < root.val and p.val < root.val:
                root = root.left
            # 如果p和q分布在root两侧，或者其中之一就是root，那么root就是最近公共祖先
            else:
                break
        return root