75.二叉搜索树额最近公共祖先

题目

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路

迭代：
1.循环搜索： 当节点 root 为空时跳出；

• 当 p, q都在 root 的 右子树 中，则遍历至 root.right ；
• 否则，当 p, q都在 root 的 左子树中，则遍历至 root.left ；
• 否则，说明找到了 最近公共祖先 ，跳出。

2.返回值： 最近公共祖先 root 。

代码

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while root:
            if root.val < p.val and root.val < q.val: # p,q 都在 root 的右子树中
                root = root.right # 遍历至右子节点
            elif root.val > p.val and root.val > q.val: # p,q 都在 root 的左子树中
                root = root.left # 遍历至左子节点
            else: break
        return root