450. 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值key，删除二叉搜索树中的key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

示例 1:

输入： root = 5,3,6,2,4,null,7, key = 3 输出：5,4,6,2,null,null,7解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。一个正确的答案是 5,4,6,2,null,null,7, 如下图所示。另一个正确答案是 5,2,6,null,4,null,7。
图片

示例 2:

输入: root = 5,3,6,2,4,null,7, key = 0 输出: 5,3,6,2,4,null,7解释: 二叉树不包含值为 0 的节点

示例 3:

输入: root = , key = 0 输出:

提示:

节点数的范围 [0, 104].
-105 <= Node.val <= 105
节点值唯一
root 是合法的二叉搜索树
-105 <= key <= 105

参考解法

下面保留的是原始练习仓库中的个人作答，可在右侧工作台中独立重写，再按需揭示对照。

python


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def deleteNode(self, root, key):
        # 找到删除节点右子树的最小值，替换删除节点位置
        if not root:
            return None
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
        else:
            if not root.left or not root.right:
                root = root.left if root.left else root.right
            else:
                cur = root.right
                while cur.left:
                    cur = cur.left
                root.val = cur.val
                root.right = self.deleteNode(root.right, cur.val)
        return root
        """
        :type root: Optional[TreeNode]
        :type key: int
        :rtype: Optional[TreeNode]
        """