LeetCode 669中等BST

修剪二叉搜索树图解题解

Q: 它和「删除 BST 中的节点」(lc450)有什么区别?

lc450 删一个指定值的节点,要处理「被删点有两个孩子」时用前驱或后继替换的复杂情形;本题是按区间 [low, high] 批量裁剪,完全靠 BST 有序性「整段取舍」——越界节点直接用它在界内一侧的子树顶替,递归一遍即可,逻辑简单得多。

Q: 能不能不用递归、做到 O(1) 额外空间?

可以。先把根往区间里挪:根太小就 root = root.right、太大就 root = root.left,直到根落在 [low, high]。然后从根出发,沿左边界不断裁掉「左孩子太小」的情况、沿右边界裁掉「右孩子太大」的情况。本质和递归一样,只是手动维护指针,省掉递归栈。

这道题到底在问什么

给定二叉搜索树的根 root 和区间 [low, high],删除树中所有值不在 [low, high] 内的节点,返回修剪后树的根。保证剩余节点构成的相对结构不变,结果仍是合法 BST。

输入: root=[1,0,2], low=1, high=2
输出: [1,null,2]
输入: root=[3,0,4,null,2,null,null,1], low=1, high=3
输出: [3,2,null,1]

最优解：一步一步想明白

3记住「太小丢自己+左子树、换右边;太大丢自己+右子树、换左边;在范围内才递归剪左右」,下面逐帧套它。
4[low, high] = [35, 65]先看这棵 BST:根 50,左边 30(挂着 20、40)、右边 70(挂着 60、80)。要保留的区间是 [35, 65],我们从根开始递归修剪。
5[low, high] = [35, 65]先找感觉:BST 里任何节点,它的左子树整棵都比它小、右子树整棵都比它大。所以一个节点一旦越界,它越界那一侧的整棵子树必然也越界,可以整段丢——这正是本题能一遍 O(n) 裁完的根。
6[low, high] = [35, 65]从根 50 开始。50 落在 [35, 65] 里,是要保留的节点。
7[low, high] = [35, 65]50 保留(标绿)。接下来按规则,要分别去修剪它的左子树和右子树。
8[low, high] = [35, 65]先修剪左子树,来到 30。先和下界 35 比一比。
9[low, high] = [35, 65]30 < 35,比下界还小,30 这个节点越界,必须丢掉。
10[low, high] = [35, 65]更关键的是:BST 里 30 的整个左子树(这里是 20)都比 30 还小,自然也都 < 35。所以 30 连同它的左边 20 整段都丢掉,只可能在它的右子树里还有合格的节点。
11[low, high] = [35, 65]于是把 50 的左孩子改接到 30 的右子树 40 上,30 和 20 已不在树里。现在继续修剪新接上来的 40。
12[low, high] = [35, 65]40 落在 [35, 65] 里,保留。
13[low, high] = [35, 65]40 保留(标绿)。它没有左右孩子,继续递归下去都是空,左子树这一支就修剪完了。
14[low, high] = [35, 65]左子树这一支全部处理完,50 的左边现在挂的就是 40。接下来回到 50,去修剪它的右子树。
15[low, high] = [35, 65]左边修好,回到 50 修剪右子树,来到 70。和上界 65 比一比。
16[low, high] = [35, 65]70 > 65,比上界还大,70 越界,要丢掉。
17[low, high] = [35, 65]同样地,BST 里 70 的整个右子树(这里是 80)都比 70 还大、也都 > 65,所以 70 连同右边 80 整段丢掉,只可能在它的左子树里还有合格节点。
18[low, high] = [35, 65]所以只保留 70 的左子树 60 这一支,把它接到 50 的右边顶替 70 的位置。70 和 80 即将从树上离开。
19[low, high] = [35, 65]把 50 的右孩子改接到 70 的左子树 60 上,70 和 80 已不在树里。继续修剪 60。
20[low, high] = [35, 65]60 落在 [35, 65] 里,保留。
21[low, high] = [35, 65]60 保留(标绿)。它也是叶子,右子树这一支修剪完成。
22[low, high] = [35, 65]整棵树修剪完成:只剩 50、40、60 三个节点,而且它们原来的相对位置(40 在左、60 在右)保持不变。
23[low, high] = [35, 65]验证一下:修剪后中序遍历是 40、50、60,严格升序、仍是合法 BST,且每个值都落在 [35, 65] 里,符合要求。
24[low, high] = [35, 65]回头看:每到一个节点,值太小就连同左子树一起丢、换上修剪后的右子树;值太大就连同右子树一起丢、换上左子树;在范围内才保留并递归修剪左右。BST 的有序性让我们能「整段剪」,一遍递归 O(n) 就裁好了。

⚠️ 容易写错的地方

✗ 错：越界节点只删自己、却保留它的两棵子树

✓ 对：val < low 时连左子树一起丢、只接右子树(val > high 反之)

BST 里左子树所有值都 < 当前节点,当前已 < low,左子树整段都越界,必须一起丢

✗ 错：修剪后忘了把返回值接回父节点

✓ 对：一律写 root.left = trim(root.left, ...) 用返回值重接

子树根越界时 trim 返回的是它的某个孩子,不重接父节点就还指向被丢弃的旧根

✗ 错：先收集区间内的值再重建一棵树

✓ 对：直接在原树上递归裁剪指针

BST 有序,靠上下界整段取舍即可,不必重建,O(n) 一遍完成

完整代码（Python / C++ / Java）

Python

from typing import List, Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if not root: return None
        if root.val < low: return self.trimBST(root.right, low, high)
        if root.val > high: return self.trimBST(root.left, low, high)
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        return root

C++

#include <algorithm>
#include <climits>
#include <functional>
#include <iterator>
#include <numeric>
#include <vector>
using namespace std;
struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode():val(0),left(nullptr),right(nullptr){} TreeNode(int x):val(x),left(nullptr),right(nullptr){} TreeNode(int x,TreeNode*l,TreeNode*r):val(x),left(l),right(r){}};
class Solution{public: TreeNode* trimBST(TreeNode* root,int low,int high){ if(!root)return nullptr; if(root->val<low)return trimBST(root->right,low,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; }};

Java

import java.util.*;
class TreeNode{int val;TreeNode left,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; if(root.val<low)return trimBST(root.right,low,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; } }

复杂度

时间

O(n)

每个节点最多被访问一次(被裁掉的整段子树直接跳过,不再深入),n 是节点数

空间

O(h)

递归栈深度等于树高 h;最坏树退化成链时 O(n),平衡时 O(log n)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着修剪二叉搜索树的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

它和「删除 BST 中的节点」(lc450)有什么区别?+

lc450 删一个指定值的节点,要处理「被删点有两个孩子」时用前驱或后继替换的复杂情形;本题是按区间 [low, high] 批量裁剪,完全靠 BST 有序性「整段取舍」——越界节点直接用它在界内一侧的子树顶替,递归一遍即可,逻辑简单得多。

能不能不用递归、做到 O(1) 额外空间?+

可以。先把根往区间里挪:根太小就 root = root.right、太大就 root = root.left,直到根落在 [low, high]。然后从根出发,沿左边界不断裁掉「左孩子太小」的情况、沿右边界裁掉「右孩子太大」的情况。本质和递归一样,只是手动维护指针,省掉递归栈。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把修剪二叉搜索树一步步讲透（全站 0 节语音精讲，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 669中等BST

修剪二叉搜索树图解题解

这道题到底在问什么

输入: root=[1,0,2], low=1, high=2
输出: [1,null,2]
输入: root=[3,0,4,null,2,null,null,1], low=1, high=3
输出: [3,2,null,1]

最优解：一步一步想明白

3记住「太小丢自己+左子树、换右边;太大丢自己+右子树、换左边;在范围内才递归剪左右」,下面逐帧套它。
4[low, high] = [35, 65]先看这棵 BST:根 50,左边 30(挂着 20、40)、右边 70(挂着 60、80)。要保留的区间是 [35, 65],我们从根开始递归修剪。
5[low, high] = [35, 65]先找感觉:BST 里任何节点,它的左子树整棵都比它小、右子树整棵都比它大。所以一个节点一旦越界,它越界那一侧的整棵子树必然也越界,可以整段丢——这正是本题能一遍 O(n) 裁完的根。
6[low, high] = [35, 65]从根 50 开始。50 落在 [35, 65] 里,是要保留的节点。
7[low, high] = [35, 65]50 保留(标绿)。接下来按规则,要分别去修剪它的左子树和右子树。
8[low, high] = [35, 65]先修剪左子树,来到 30。先和下界 35 比一比。
9[low, high] = [35, 65]30 < 35,比下界还小,30 这个节点越界,必须丢掉。
10[low, high] = [35, 65]更关键的是:BST 里 30 的整个左子树(这里是 20)都比 30 还小,自然也都 < 35。所以 30 连同它的左边 20 整段都丢掉,只可能在它的右子树里还有合格的节点。
11[low, high] = [35, 65]于是把 50 的左孩子改接到 30 的右子树 40 上,30 和 20 已不在树里。现在继续修剪新接上来的 40。
12[low, high] = [35, 65]40 落在 [35, 65] 里,保留。
13[low, high] = [35, 65]40 保留(标绿)。它没有左右孩子,继续递归下去都是空,左子树这一支就修剪完了。
14[low, high] = [35, 65]左子树这一支全部处理完,50 的左边现在挂的就是 40。接下来回到 50,去修剪它的右子树。
15[low, high] = [35, 65]左边修好,回到 50 修剪右子树,来到 70。和上界 65 比一比。
16[low, high] = [35, 65]70 > 65,比上界还大,70 越界,要丢掉。
17[low, high] = [35, 65]同样地,BST 里 70 的整个右子树(这里是 80)都比 70 还大、也都 > 65,所以 70 连同右边 80 整段丢掉,只可能在它的左子树里还有合格节点。
18[low, high] = [35, 65]所以只保留 70 的左子树 60 这一支,把它接到 50 的右边顶替 70 的位置。70 和 80 即将从树上离开。
19[low, high] = [35, 65]把 50 的右孩子改接到 70 的左子树 60 上,70 和 80 已不在树里。继续修剪 60。
20[low, high] = [35, 65]60 落在 [35, 65] 里,保留。
21[low, high] = [35, 65]60 保留(标绿)。它也是叶子,右子树这一支修剪完成。
22[low, high] = [35, 65]整棵树修剪完成:只剩 50、40、60 三个节点,而且它们原来的相对位置(40 在左、60 在右)保持不变。
23[low, high] = [35, 65]验证一下:修剪后中序遍历是 40、50、60,严格升序、仍是合法 BST,且每个值都落在 [35, 65] 里,符合要求。
24[low, high] = [35, 65]回头看:每到一个节点,值太小就连同左子树一起丢、换上修剪后的右子树;值太大就连同右子树一起丢、换上左子树;在范围内才保留并递归修剪左右。BST 的有序性让我们能「整段剪」,一遍递归 O(n) 就裁好了。

⚠️ 容易写错的地方

✗ 错：越界节点只删自己、却保留它的两棵子树

✓ 对：val < low 时连左子树一起丢、只接右子树(val > high 反之)

BST 里左子树所有值都 < 当前节点,当前已 < low,左子树整段都越界,必须一起丢

✗ 错：修剪后忘了把返回值接回父节点

✓ 对：一律写 root.left = trim(root.left, ...) 用返回值重接

子树根越界时 trim 返回的是它的某个孩子,不重接父节点就还指向被丢弃的旧根

✗ 错：先收集区间内的值再重建一棵树

✓ 对：直接在原树上递归裁剪指针

BST 有序,靠上下界整段取舍即可,不必重建,O(n) 一遍完成

完整代码（Python / C++ / Java）

Python

from typing import List, Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if not root: return None
        if root.val < low: return self.trimBST(root.right, low, high)
        if root.val > high: return self.trimBST(root.left, low, high)
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        return root

C++

#include <algorithm>
#include <climits>
#include <functional>
#include <iterator>
#include <numeric>
#include <vector>
using namespace std;
struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode():val(0),left(nullptr),right(nullptr){} TreeNode(int x):val(x),left(nullptr),right(nullptr){} TreeNode(int x,TreeNode*l,TreeNode*r):val(x),left(l),right(r){}};
class Solution{public: TreeNode* trimBST(TreeNode* root,int low,int high){ if(!root)return nullptr; if(root->val<low)return trimBST(root->right,low,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; }};

Java

import java.util.*;
class TreeNode{int val;TreeNode left,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; if(root.val<low)return trimBST(root.right,low,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; } }

复杂度

时间

O(n)

每个节点最多被访问一次(被裁掉的整段子树直接跳过,不再深入),n 是节点数

空间

O(h)

递归栈深度等于树高 h;最坏树退化成链时 O(n),平衡时 O(log n)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着修剪二叉搜索树的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

它和「删除 BST 中的节点」(lc450)有什么区别?+

能不能不用递归、做到 O(1) 额外空间?+

想听吴师兄把这道题讲给你听？

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

修剪二叉搜索树 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

修剪二叉搜索树 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

修剪二叉搜索树图解题解

修剪二叉搜索树图解题解