当前位置：首页 > news >正文

LeetCode 450. Delete Node in a BST 题解

news 2026/6/24 20:45:26

LeetCode 450. Delete Node in a BST 题解

题目描述

给定一个二叉搜索树的根节点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 输出：[]

解题思路

方法：递归

思路：

利用二叉搜索树的性质：左子树的所有节点值小于根节点的值，右子树的所有节点值大于根节点的值
递归地删除目标节点：
- 如果当前节点为空，返回null
- 如果当前节点的值大于目标值，递归删除左子树中的目标节点
- 如果当前节点的值小于目标值，递归删除右子树中的目标节点
- 如果当前节点的值等于目标值：
  - 如果当前节点没有左子节点，返回右子节点
  - 如果当前节点没有右子节点，返回左子节点
  - 否则，找到右子树中的最小节点（即右子树的最左节点），将其值赋给当前节点，然后递归删除右子树中的最小节点

复杂度分析：

时间复杂度：O(h)，其中 h 是二叉搜索树的高度。在最坏情况下，二叉搜索树退化为链表，时间复杂度为 O(n)。
空间复杂度：O(h)，递归调用的栈空间取决于二叉搜索树的高度。

代码实现

方法：递归

# 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]: # 递归终止条件：如果当前节点为空，返回 null 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: return root.right # 如果当前节点没有右子节点，返回左子节点 elif not root.right: return root.left # 否则，找到右子树中的最小节点（即右子树的最左节点） else: # 找到右子树的最左节点 min_node = self.find_min(root.right) # 将最小节点的值赋给当前节点 root.val = min_node.val # 递归删除右子树中的最小节点 root.right = self.deleteNode(root.right, min_node.val) return root # 找到以 node 为根的子树中的最小节点（即最左节点） def find_min(self, node): while node.left: node = node.left return node