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, val0, leftNone, rightNone): # 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测试用例测试用例 1输入root [5,3,6,2,4,null,7], key 3输出[5,4,6,2,null,null,7]测试用例 2输入root [5,3,6,2,4,null,7], key 0输出[5,3,6,2,4,null,7]测试用例 3输入root [], key 0输出[]总结本题是二叉搜索树的经典问题主要考察对二叉搜索树性质的理解和应用。通过使用递归我们可以高效地在二叉搜索树中删除目标节点。递归的核心思想是利用二叉搜索树的性质递归地删除目标节点。当找到目标节点时根据其是否有子节点的情况进行处理确保删除后