个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰今天又到了我们的每日刷题环节主要还是二叉搜索树相关的题目。摘要本文介绍了如何在二叉搜索树(BST)中删除指定节点的算法。通过递归方法根据节点子节点情况分为四种处理方式无子节点直接删除只有左/右子节点时用子节点替代有两个子节点时找到右子树最小值替换并删除原节点。文章详细解析了递归过程中树的连接逻辑并通过示例演示了删除叶子节点、单子节点和双子节点的具体操作。最后给出了递归和迭代两种实现方案时间复杂度为O(h)h为树的高度。该算法能有效维护BST的性质适用于各类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输出:[]提示:节点数的范围[0, 104].-105 Node.val 105节点值唯一root是合法的二叉搜索树-105 key 105进阶要求算法时间复杂度为 O(h)h 为树的高度。题目解析拿到这道题目我们看到二叉搜索树就要利用他的特殊性质这对我们解题很有帮助可以简化我们的代码和逻辑。给定一个二叉搜索树的根节点root和一个值key删除二叉搜索树中的key对应的节点并保证删除后树仍然是二叉搜索树。返回删除后树的根节点。注意题目不要求保持树的形状完全不变只要满足BST性质即可。核心难点插入节点永远在叶子位置很简单。但删除节点可能在任意位置被删除的节点可能有0个、1个或2个子节点删除后还要保持BST性质那第一步我们肯定是要先找到要删除的节点之后我们才能考虑后续的树 的 结构是怎么改变的。利用BST性质查找如果key root.val去左子树找如果key root.val去右子树找如果key root.val就是这个节点准备删除第二步就是找到之后该怎么处理这个节点的问题了删除这个节点当然很简单但是删除之后树的连接是怎么实现的值得思考。根据子节点情况分类删除情况描述处理方法情况1没有子节点叶子节点直接删除返回 null情况2只有左子节点用左子节点代替自己情况3只有右子节点用右子节点代替自己情况4有两个子节点找到右子树的最小节点或左子树的最大节点替换值然后删除那个节点情况4的详细说明当要删除的节点有两个孩子时怎么保持BST性质方法找后继节点右子树中的最小值要删除节点5 5 / \ 3 8 / / \ 2 6 9 \ 7 步骤 1. 找到右子树(8)中的最小值 6 2. 把5的值改成6 3. 去右子树删除原来的6此时的6是叶子或只有一个右孩子为什么这样做右子树的最小值一定大于左子树的所有节点右子树的最小值一定小于右子树的其他节点用它替换后BST性质仍然满足我们这里选用递归法将左右子树分开遍历把修改后的子树返回给父节点同时还可以做删除节点之后的连接逻辑。其实整体思路是这样乍一看没啥难度但难得是如果处理删除节点之后树的构建或者说是树的连接。具体分析就拿在左子树中查找并删除1.我们通过和根节点进行比较之后确定了要删除的节点在左子树。2.然后我们通过递归一次向下查找看这个要删除的节点是在左子树的子左子树还是子右子树。依次向下。3.当左右都没有找到也就是两个if判断都没成立时这是也就是找到了要删除的节点因为keyroot.val因为一共就三种情况要么大于要么小于要么等于。4.这只是简单的找到我们在每步递归的逻辑是每层递归的三个核心逻辑逻辑A接收并处理下层返回的结果javaroot.left deleteNode(root.left, key); // 或 root.right deleteNode(root.right, key);作用下层递归删除节点后可能会返回一个新的子树根节点当前层要用这个新节点替换原来的左/右孩子。逻辑B向上层返回我这一层处理完的结果javareturn root;作用告诉上层调用者我是经过处理后的当前节点请把我连接到你的对应位置。逻辑C找到目标时执行删除并返回替代节点java// 情况1没有左孩子 if (root.left null) return root.right; // 情况2没有右孩子 if (root.right null) return root.left; // 情况3有两个孩子...作用删除当前节点返回能够替代它的节点可能是孩子、后继、前驱最后一层递归的结束条件就是删除节点之后如何连接替代节点的逻辑之后整个递归调用链的逐层返回三种情况的深层解析情况1叶子节点java // 节点2没有孩子 if (root.left null) return root.right; // root.right null // 返回 null情况2只有一个孩子java // 节点2只有右孩子 if (root.left null) return root.right; // 返回右孩子节点 // 返回节点比如节点3情况3有两个孩子java // 节点2有两个孩子 TreeNode successor findMin(root.right); root.val successor.val; root.right deleteNode(root.right, successor.val); return root; // 返回当前节点值已被替换 // 返回修改后的节点2递归中每一层的root.left ...就是重新连接的操作也就是我们删除节点之后树的连接操作通过改变节点的指针指向进行构建从删除点开始自底向上地重新构建连接树的每一个节点。例子示例1删除叶子节点原始树text10 / \ 5 15 / \ 2 7目标删除key 2叶子节点递归过程追踪text第1层deleteNode(10, 2) │ 2 10向左 └─→ root.left deleteNode(5, 2) 第2层deleteNode(5, 2) │ 2 5向左 └─→ root.left deleteNode(2, 2) 第3层deleteNode(2, 2) ← 找到了 │ key root.val │ 检查root.left nullroot.right null └─→ return null (返回替代者null) 第2层收到 null │ root.left null ← 指针改变原来指向节点2现在指向null │ return 节点5 第1层收到 节点5 │ root.left 节点5 (节点5没变但它的left已经是null了) └─→ return 节点10指针变化图删除前text节点10.left ──→ 节点5 节点5.left ──→ 节点2 节点2.left ──→ null 节点2.right ──→ null删除后第2层执行root.left null后text节点10.left ──→ 节点5 节点5.left ──→ null ← 原来的指向被改变了 节点2 ← 没有任何指针指向它会被GC回收示例2删除只有一个孩子的节点原始树text10 / \ 5 15 / \ 2 7 \ 9目标删除key 7只有右孩子9递归过程追踪text第1层deleteNode(10, 7) │ 7 10向左 └─→ root.left deleteNode(5, 7) 第2层deleteNode(5, 7) │ 7 5向右 └─→ root.right deleteNode(7, 7) 第3层deleteNode(7, 7) ← 找到了 │ key root.val │ root.left nullroot.right 节点9 └─→ return root.right (返回替代者节点9) 第2层收到 节点9 │ root.right 节点9 ← 指针改变原来指向节点7现在指向节点9 │ return 节点5 第1层收到 节点5 │ root.left 节点5 (节点5没变但它的right指向9了) └─→ return 节点10指针变化图删除前text节点5.right ──→ 节点7 节点7.right ──→ 节点9删除后第2层执行root.right 节点9text节点5.right ──→ 节点9 ← 直接跳过了节点7 节点7 ← 没有任何指针指向它最终树text10 / \ 5 15 / \ 2 9示例3删除有两个孩子的节点最复杂原始树text10 / \ 5 15 / \ 3 8 / \ 7 9目标删除key 5有两个孩子递归过程追踪text第1层deleteNode(10, 5) │ 5 10向左 └─→ root.left deleteNode(5, 5) 第2层deleteNode(5, 5) ← 找到了 │ key root.val │ 有两个孩子走情况3 │ │ 1. 找后继findMin(节点8) → 节点7 │ 2. 替换值root.val 7 (节点5的值变成7) │ 3. 删除后继节点 │ root.right deleteNode(8, 7) │ └─→ 先进入第3层等待返回值 第3层deleteNode(8, 7) │ 7 8向左 └─→ root.left deleteNode(7, 7) 第4层deleteNode(7, 7) ← 找到后继原节点 │ key root.val │ 节点7是叶子左右都是null └─→ return null 第3层收到 null │ root.left null ← 指针改变原来指向节点7现在指向null │ return 节点8 第2层收到 节点8 │ root.right 节点8 (节点8的left已经是null了) │ return 节点5 (此时节点5的值已经是7了) 第1层收到 节点5 │ root.left 节点5 └─→ return 节点10指针变化图删除前text节点10.left ──→ 节点5 节点5.left ──→ 节点3 节点5.right ──→ 节点8 节点8.left ──→ 节点7替换值后节点5.val 7text节点5 现在存储的值是7 节点8.left ──→ 节点7 (等待被删除)删除后继后第3层执行root.left nulltext节点8.left ──→ null ← 断开了节点7最终树结构text节点10.left ──→ 节点5 (值是7) 节点5.left ──→ 节点3 节点5.right ──→ 节点8 节点8.left ──→ null 节点8.right ──→ 节点9最终树text10 / \ 7 15 / \ 3 8 \ 9题目答案class Solution { public TreeNode deleteNode(TreeNode root, int key) { // 基础情况没找到要删除的节点 if (root null) { return null; } // 在左子树中查找并删除 if (key root.val) { root.left deleteNode(root.left, key); return root; } // 在右子树中查找并删除 if (key root.val) { root.right deleteNode(root.right, key); return root; } // 找到了要删除的节点root.val key // 情况1和2没有左孩子直接返回右孩子右孩子可能是null或一个节点 if (root.left null) { return root.right; } // 情况3没有右孩子直接返回左孩子 if (root.right null) { return root.left; } // 情况4有两个孩子 // 找到右子树的最小节点后继节点 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; } }迭代法class Solution { public TreeNode deleteNode(TreeNode root, int key) { TreeNode parent null; TreeNode current root; // 1. 找到要删除的节点及其父节点 while (current ! null current.val ! key) { parent current; if (key current.val) { current current.left; } else { current current.right; } } // 没找到 if (current null) { return root; } // 2. 删除current节点 TreeNode newChild deleteNodeAndGetReplacement(current); // 3. 连接到父节点 if (parent null) { return newChild; // 删除的是根节点 } if (parent.left current) { parent.left newChild; } else { parent.right newChild; } return root; } private TreeNode deleteNodeAndGetReplacement(TreeNode node) { // 情况1没有左孩子 if (node.left null) { return node.right; } // 情况2没有右孩子 if (node.right null) { return node.left; } // 情况3有两个孩子 // 找到右子树的最小节点后继 TreeNode successor node.right; TreeNode successorParent node; while (successor.left ! null) { successorParent successor; successor successor.left; } // 用后继节点的值替换 node.val successor.val; // 删除后继节点 if (successorParent node) { successorParent.right successor.right; } else { successorParent.left successor.right; } return node; } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励
