日野弥生：勉強しよう
LeetCode 450 - 删除二叉搜索树中的节点
发表于2025年03月19日
根据二叉搜索树的定义，删除节点时：
- 如果目标节点没有子节点，可以直接移除该目标节点。
- 如果目标节只有一个子节点，可以用其子节点作为替换。
- 如果目标节点有两个子节点，需要用其中序后继节点或者前驱节点来替换，再删除该目标节点。(关键在于后继节点和前驱节点如何找)
所以，这样就有两种处理方案：
- 左子树里最右边的节点就是他的前驱节点；
- 右子树里最左边的节点就是他的后继节点。
按照第一种方案实现
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root:
return None
# 该值不等于当前节点时，递归下去处理
if key < root.val:
root.left = self.deleteNode(root.left, key)
elif key == root.val:
# 仅有一个节点，当且节点接入他的子节点
if not root.left or not root.right:
root = root.left if root.left else root.right
else:
# 先找到左子树
successor = root.left
# 拿到左子树的最右节点，即curr的前驱节点
while successor.right:
successor = successor.right
# curr的左子树递归删除该节点
successor.left = self.deleteNode(root.left, successor.val)
# 右子树不变
successor.right = root.right
return successor
else:
# 该值不等于当前节点时，递归下去处理
root.right = self.deleteNode(root.right, key)
return root按照第二种方案实现
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root:
return None
if key < root.val:
root.left = self.deleteNode(root.left, key)
elif key == root.val:
if not root.left or not root.right:
root = root.left if root.left else root.right
else:
successor = root.right
while successor.left:
successor = successor.left
successor.right = self.deleteNode(root.right, successor.val)
successor.left = root.left
return successor
else:
root.right = self.deleteNode(root.right, key)
return root