应用题-二叉树专题-删除二叉搜索树中的节点
- 版权声明：本站原创文章，于2026-04-13，由 管理员 发表。
- 转载请注明： 应用题-二叉树专题-删除二叉搜索树中的节点 | CodeGarden
```python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
# 删除一个节点后 要保证其依旧是二叉搜索树
if not root: return None
# 没找到节点 不操作
# 如果删除的是叶子节点 直接删除
# 如果删除的不是叶子节点
# - 删除节点的右子树为空 左子树直接挂到父节点下
# - 删除节点的左子树为空 右子树直接挂到父节点下
# - 删除节点的左右子树都存在 取删除节点右子树上 最左端的叶子结点 和删除节点交换 删除交换后的叶子结点
r = root
p = None # r的父节点
# 寻找目标节点 以及父节点
while r:
if r.val == key:
found = True
break
p = r
if r.val > key: r = r.left
else: r = r.right
# 0 未找到节点
if not r: return root
# 1 叶子结点
if not r.left and not r.right:
# 删除的是根节点
if not p:
return None
if p.left == r: p.left = None
else: p.right = None
# 2 左右子树均存在
elif r.left and r.right:
# r的右子树的最左端节点作为新的r
px = r
cx = r.right
while cx.left:
px = cx
cx = cx.left
r.val = cx.val
# 若节点存在右子树 将右子树挂到父节点上
if px.left == cx:
px.left = cx.right
else: px.right = cx.right
# 3 左右子树只存在一个
elif not r.left:
# 删除的是根节点
if not p:
return r.right
# 需要知道挂载p的left还是right
if p.left == r: p.left = r.right
elif p.right == r: p.right = r.right
elif not r.right:
# 删除的是根节点
if not p:
return r.left
if p.left == r: p.left = r.left
elif p.right == r: p.right = r.left
return root
```