代码随想录第二十天刷题

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        return self.traversal(root, p, q)

    def traversal(self, cur, p, q):
        if cur is None:
            return cur
        
        if cur.val > p.val and cur.val > q.val:
            left = self.traversal(cur.left, p, q)
            if left is not None:
                return left
        
        if cur.val < p.val and cur.val < q.val:
            right = self.traversal(cur.right, p, q)
            if right is not None:
                return right

        return cur 

# ---------- BST 最近公共祖先 ----------
# 核心：利用 BST 的有序性
#
# 三种情况：
# 1. p、q 都在左子树 → 去左子树
# 2. p、q 都在右子树 → 去右子树
# 3. 否则 → 当前节点就是 LCA

水题