千问 LeetCode 450. 删除二叉搜索树中的节点 Java实现

这道题是 BST 操作中的经典题核心难点在于删除节点后如何维护 BST 的性质。题目简述给定一个二叉搜索树的根节点 root 和一个值 key删除树中值为 key 的节点并返回更新后的根节点。核心思路删除节点分三种情况叶子节点直接删除返回 null。只有一个子节点用子节点替代当前节点。有两个子节点这是最复杂的情况。通常用中序后继右子树的最小节点或中序前驱左子树的最大节点来替代当前节点的值然后递归删除那个后继/前驱节点。这里采用中序后继方案找到右子树中的最小节点用它的值覆盖当前节点然后删除右子树中的那个最小节点。Java 实现class Solution {public TreeNode deleteNode(TreeNode root, int key) {if (root null) return null;if (key root.val) { // 目标在左子树 root.left deleteNode(root.left, key); } else if (key root.val) { // 目标在右子树 root.right deleteNode(root.right, key); } else { // 找到目标节点 // 情况1叶子节点或只有一个子节点 if (root.left null) return root.right; if (root.right null) return root.left; // 情况2有两个子节点找右子树的最小节点中序后继 TreeNode successor findMin(root.right); root.val successor.val; // 删除右子树中的后继节点 root.right deleteNode(root.right, successor.val); } return root; } // 找到以 node 为根的子树中的最小节点 private TreeNode findMin(TreeNode node) { while (node.left ! null) { node node.left; } return node; }}复杂度分析时间复杂度O(h)其中 h 是树的高度。最坏情况退化为链表为 O(n)平衡树为 O(log n)。空间复杂度O(h)递归栈的深度。面试易错点有两个子节点时不能简单地用左子树或右子树替代必须找到中序后继/前驱来保持 BST 性质。递归返回值每次递归都要返回更新后的子树根节点父节点通过 root.left … 或 root.right … 来接住。找最小节点右子树的最小节点一定是最左边的节点一路往左走即可。面试延伸为什么选右子树最小节点因为它比当前节点大满足右子树性质又比右子树其他节点小可以放在当前节点位置。迭代实现也可以用迭代方式完成但代码会更复杂需要记录父节点。AVL / 红黑树实际工程中删除节点可能涉及旋转平衡但 LeetCode 450 不要求自平衡。需要我接着为你讲解 LeetCode 701. 二叉搜索树中的插入操作 的对比实现吗