【LeetCode刷题日记】669.修剪二叉搜索树

🔥个人主页：北极的代码（欢迎来访）
🎬作者简介：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

第一步：根节点 3

• 3 在 [1,3] 内 → 保留

• 递归修剪左子树（根为 0）

第二步：节点 0

• 0 < low (1) → 全部删除，返回修剪后的右子树（根为 2）

• 节点 3 的左指针指向 2

第三步：节点 2

• 2 在 [1,3] 内 → 保留

• 递归修剪左子树（根为 1）

第四步：节点 1

• 1 在 [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：删除节点并连接左子树的节点

原始树：

text

5 / \ 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（整棵子树删除）

原始树：

text

3 / \ 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被丢弃。

但如果右子树也不符合呢：

原始树：

text

2 \ 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。

总结表格

关键理解：

1. 返回值= "修剪后应该放在这个位置的节点"

2. 删除= 通过改变父节点的指向来实现

3. 连接= 通过递归返回值自动完成，不需要手动操作

迭代写法

也可以用迭代 + 双指针实现：

1. 先处理根节点：如果根节点值小于 low，一直往右走找到第一个 ≥ low 的节点作为新根；如果根节点值大于 high，一直往左走找到第一个 ≤ high 的节点作为新根。

2. 处理左子树：从根节点开始，对每个节点的左子节点，如果左子节点值 < low，就跳过这个左子节点（直接指向左子节点的右孩子）。

3. 处理右子树：类似地，对每个节点的右子节点，如果右子节点值 > 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 root's 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 root's 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; } }

结语：

如果对你有帮助，请点赞，关注，收藏，我会持续更新的！