前往此题

递归法

二叉搜索树祖先的定义：

若节点p在节点root的左或者右子树中，或者p=root，则称root是p的祖先。

根据祖先的定义，可以分析出以下几种情况：

1. q和p在root左右两边，此时它们的祖先就是root
2. 当root.val < p.val, 则p在root 的右子树中
3. 当root.val > p.val，则p在root的左子树中

代码

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        if root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        return root

复杂度分析

• 时间复杂度： O(N)
• 空间复杂度： O(N)

迭代法

迭代法的思路与递归法相同

1. 遍历查找节点
   • 通过判断大小确定p,q在root的左侧还是右侧，在左子树就遍历root.left, 在右侧就遍历root.right
   • 如果在两侧，root就是公共祖先节点
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:
                root = root.right
            elif root.val > p.val and root.val > q.val:
                root = root.left
            else: break
        return root

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度: O(N)