个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰今天星期五在这里提前祝大家周末快乐现在来到了我们每日的刷题环节今天刷的是二叉搜索树的相关算法题。摘要这篇文章讲解了如何修剪二叉搜索树BST使其所有节点的值都在给定区间[low, high]内。关键点包括1利用BST的性质左子树值小右子树值大来决定是否需要修剪子树2递归处理四种情况节点值小于low、大于high、在区间内或为空3通过示例和图解演示修剪过程4提供了递归和迭代两种实现方法。最终返回修剪后的BST保持原有结构不变。时间复杂度为O(n)空间复杂度递归为O(h)迭代为O(1)。题目背景669.修改二叉搜索树给你二叉搜索树的根节点root同时给定最小边界low和最大边界high。通过修剪二叉搜索树使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构 (即如果没有被移除原有的父代子代关系都应当保留)。 可以证明存在唯一的答案。所以结果应当返回修剪好的二叉搜索树的新的根节点。注意根节点可能会根据给定的边界发生改变。示例 1输入root [1,0,2], low 1, high 2输出[1,null,2]示例 2输入root [3,0,4,null,2,null,null,1], low 1, high 3输出[3,2,null,1]提示树中节点数在范围[1, 104]内0 Node.val 104树中每个节点的值都是唯一的题目数据保证输入是一棵有效的二叉搜索树0 low high 104题目解析首先我们先要明白题目的意思给你一棵二叉搜索树和一个区间[low, high]需要删除所有值 low 或 high 的节点保留值在[low, high]内的节点删除后的树仍然是一棵 BST关键点因为是 BST所以节点的左子树所有值都 该节点值右子树所有值都 该节点值。这个性质可以帮助我们快速定位哪些子树可以整体删除。所以这里也用到了节点的删除具体的步骤跟我们前几天学习的二叉搜索树的删除一个流程。我们主要还是用递归进行实现递归思路拆解我们用一个递归函数trimBST(root, low, high)来修剪以root为根的子树返回修剪后的子树的根节点。情况 1根节点为空java if (root null) return null;情况 2当前节点值 low因为 BST 的性质当前节点 low左子树所有节点更小也 low右子树可能有 low 的节点所以当前节点和左子树全部需要删除直接返回trimBST(root.right, low, high)。java if (root.val low) { return trimBST(root.right, low, high); }情况 3当前节点值 high同理当前节点 high右子树所有节点更大也 high左子树可能有 high 的节点所以当前节点和右子树全部删除直接返回trimBST(root.left, low, high)。java if (root.val high) { return trimBST(root.left, low, high); }情况 4当前节点在 [low, high] 范围内当前节点保留但是它的左右子树中可能还有不满足条件的节点需要递归修剪。java root.left trimBST(root.left, low, high); root.right trimBST(root.right, low, high); return root;图解示例输入text 3 / \ 0 4 \ 2 / 1 low 1, high 3第一步根节点 33 在 [1,3] 内 → 保留递归修剪左子树根为 0第二步节点 00 low (1) → 全部删除返回修剪后的右子树根为 2节点 3 的左指针指向 2第三步节点 22 在 [1,3] 内 → 保留递归修剪左子树根为 1第四步节点 11 在 [1,3] 内 → 保留左右子树都为空最终树结构3 / 2 / 1 输出[3,2,null,1]节点删除后的连接机制这是最核心的部分让我用具体例子演示。例子1删除节点并连接右子树的节点原始树5 / \ 2 7 \ 4区间[3, 7]执行过程trimBST(5) { // 5在区间内保留 root.left trimBST(2, 3, 7); // ← 关键 root.right trimBST(7, 3, 7); return 5; }进入trimBST(2, 3, 7)java trimBST(2) { // 2 3进入情况2 return trimBST(2.right, 3, 7); // 2.right 节点4 }进入trimBST(4, 3, 7)java trimBST(4) { // 4在区间内保留 root.left trimBST(null, 3, 7); root.right trimBST(null, 3, 7); return 4; }回溯连接text trimBST(4) 返回 4 ↑ trimBST(2) 返回 4 ↑ root.left 4 // 节点5的左指针从指向2改为指向4结果text 5 / \ 4 7连接示意图text 删除前5.left → 2 → 4 删除后5.left → 4 (跳过了2)例子2删除节点并连接左子树的节点原始树text5 / \ 3 8 / / 2 6区间[3, 6]java trimBST(5) { root.left trimBST(3, 3, 6); root.right trimBST(8, 3, 6); // ← 关键 } trimBST(8) { // 8 6进入情况3 return trimBST(8.left, 3, 6); // 8.left 节点6 } trimBST(6) { // 6在区间内保留 return 6; }回溯text trimBST(6) 返回 6 ↑ trimBST(8) 返回 6 ↑ root.right 6 // 节点5的右指针从指向8改为指向6结果text 5 / \ 3 6例子3删除节点并返回 null整棵子树删除原始树text3 / \ 1 5区间[4, 6]java trimBST(3) { // 3 4进入情况2 return trimBST(3.right, 4, 6); // 3.right 节点5 } trimBST(5) { // 5在区间内 return 5; }结果返回节点5节点3被丢弃。但如果右子树也不符合呢原始树text2 \ 1区间[3, 5]java trimBST(2) { // 2 3 return trimBST(2.right, 3, 5); // 2.right 节点1 } trimBST(1) { // 1 3 return trimBST(1.right, 3, 5); // 1.right null } trimBST(null) { return null; }回溯trimBST(null) 返回 null ↑ trimBST(1) 返回 null ↑ trimBST(2) 返回 null结果整棵树被删除返回 null。总结表格情况返回值连接方式删除的节点root.val lowtrimBST(root.right)上层直接指向右子树的修剪结果当前节点及左子树root.val hightrimBST(root.left)上层直接指向左子树的修剪结果当前节点及右子树low ≤ root.val ≤ highroot上层保持指向当前节点无但修剪左右子树关键理解返回值 修剪后应该放在这个位置的节点删除 通过改变父节点的指向来实现连接 通过递归返回值自动完成不需要手动操作迭代写法也可以用迭代 双指针实现先处理根节点如果根节点值小于 low一直往右走找到第一个 ≥ low 的节点作为新根如果根节点值大于 high一直往左走找到第一个 ≤ high 的节点作为新根。处理左子树从根节点开始对每个节点的左子节点如果左子节点值 low就跳过这个左子节点直接指向左子节点的右孩子。处理右子树类似地对每个节点的右子节点如果右子节点值 high就跳过它指向右子节点的左孩子。迭代写法在极端深度的树上可以避免递归栈溢出但代码稍复杂面试中递归写法更清晰常用。题目答案递归法/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public TreeNode trimBST(TreeNode root, int low, int high) { if (root null) { return null; } // 如果当前节点值小于 low修剪后的树在右子树中 if (root.val low) { return trimBST(root.right, low, high); } // 如果当前节点值大于 high修剪后的树在左子树中 if (root.val high) { return trimBST(root.left, low, high); } // 当前节点在范围内递归修剪左右子树 root.left trimBST(root.left, low, high); root.right trimBST(root.right, low, high); return root; } }迭代法class Solution { //iteration public TreeNode trimBST(TreeNode root, int low, int high) { if(root null) return null; while(root ! null (root.val low || root.val high)){ if(root.val low) root root.right; else root root.left; } TreeNode curr root; //deal with roots left sub-tree, and deal with the value smaller than low. while(curr ! null){ while(curr.left ! null curr.left.val low){ curr.left curr.left.right; } curr curr.left; } //go back to root; curr root; //deal with roots righg sub-tree, and deal with the value bigger than high. while(curr ! null){ while(curr.right ! null curr.right.val high){ curr.right curr.right.left; } curr curr.right; } return root; } }结语如果对你有帮助请点赞关注收藏我会持续更新的