1
class Solution:
2
    # 相对于二叉树的最近公共祖先，这里可以使用二叉搜索树的性质来简化查找过程
3
    # 如果 p 和 q 的值都小于 root 的值，则最近公共祖先在左子树中
4
    # 如果 p 和 q 的值都大于 root 的值，则最近公共祖先在右子树中
5
    # 如果 p 和 q 的值分别在 root 的两侧，或者一个等于 root 的值，则 root 就是最近公共祖先
6
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
7
        if not root:
8
            return None
9
        # 为了避免 p.val > q.val 的情况，我们可以保证 p.val <= q.val
10
        if p.val > q.val:
11
            return self.lowestCommonAncestor(root, q, p)
12
        # 当前 root 在 p 和 q 之间，说明就是最近公共祖先
13
        if root.val >= p.val and root.val <= q.val:
14
            return root
15
        # 如果当前节点值大于 q 的值，则公共祖先一定在左子树
16
        if root.val > q.val:
17
            return self.lowestCommonAncestor(root.left, p, q)
18
        # 否则公共祖先一定在右子树
19
        else:
20
            return self.lowestCommonAncestor(root.right, p, q)

1
class Solution:
2
    # 二叉搜索树的插入操作
3
    # 如果当前节点为空，则创建一个新节点并返回
4
    # 如果当前节点的值大于要插入的值，则递归到左子树
5
    # 如果当前节点的值小于或等于要插入的值，则递归到右子树
6
    # 最终返回根节点
7
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
8
        if not root:
9
            return TreeNode(val)
10
        if root.val > val:
11
            root.left = self.insertIntoBST(root.left, val)
12
        else:
13
            root.right = self.insertIntoBST(root.right, val)
14
        return root

1
class Solution:
2
    # 二叉搜索树的删除操作有三种情况：
3
    ## 1. 如果要删除的节点没有子节点，直接删除该节点
4
    ## 2. 如果要删除的节点只有一个子节点，用该子节点替代当前节点
5
    ## 3. 如果要删除的节点有两个子节点，找到右子树的最小节点，将其值替换到当前节点，然后递归删除右子树中的最小节点
6
    # 注意：在删除操作中，需要保持二叉搜索树的性质，即左子树的值小于根节点的值，右子树的值大于根节点的值
7
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
8
        if not root:
9
            return None
10
        if root.val == key:
11
            # 情况1：左子树为空，返回右子树
12
            if not root.left:
13
                return root.right
14
            # 情况2：右子树为空，返回左子树
15
            if not root.right:
16
                return root.left
17
            # 情况3：左右子树都不为空
18
            # 找到右子树中最小的节点
19
            node = self.getMin(root.right)
20
            # 用该最小节点替换当前节点
21
            root.val = node.val
22
            # 删除右子树中已替换的那个节点
23
            root.right = self.deleteNode(root.right, node.val)
24
        elif root.val > key:
25
            root.left = self.deleteNode(root.left, key)
26
        else:
27
            root.right = self.deleteNode(root.right, key)
28
        return root
29

30
    # 获取以 root 为根的树中最小值节点
31
    def getMin(self, root: TreeNode) -> TreeNode:
32
        while root.left:
33
            root = root.left
34
        return root