当前位置：首页 > news >正文

今日算法（二叉树剪枝）

news 2026/5/25 0:28:29

题目描述

给你二叉搜索树的根节点root，同时给定最小边界low和最大边界high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。

修剪树不应该改变保留在树中的元素的相对结构（即如果没有被移除，原有的父子代关系都应当保留）
可以证明存在唯一的答案
结果应当返回修剪好的二叉搜索树的新的根节点（根节点可能会根据给定的边界发生改变）

核心思路：利用二叉搜索树的性质递归修剪

二叉搜索树（BST）的核心性质：

左子树所有节点值 < 根节点值
右子树所有节点值 > 根节点值
中序遍历结果为升序序列

基于这个性质，我们可以用递归的方式对每个节点进行判断和修剪：

如果当前节点为空，直接返回空（递归终止条件）
如果当前节点值 <low：说明当前节点和其左子树都不符合条件，直接返回右子树的修剪结果
如果当前节点值 >high：说明当前节点和其右子树都不符合条件，直接返回左子树的修剪结果
如果当前节点值在[low, high]区间内：递归修剪其左、右子树，最后返回当前节点

完整代码实现（C++）

cpp

/** * Definition for a binary tree node. * 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 *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* trimBST(TreeNode* root, int low, int high) { // 1. 递归终止条件：节点为空，直接返回 if (!root) return nullptr; // 2. 当前节点值小于low：左子树全部不符合条件，只需要修剪右子树 if (root->val < low) { return trimBST(root->right, low, high); } // 3. 当前节点值大于high：右子树全部不符合条件，只需要修剪左子树 if (root->val > high) { return trimBST(root->left, low, high); } // 4. 当前节点值在区间内：递归修剪左右子树，保留当前节点 root->left = trimBST(root->left, low, high); root->right = trimBST(root->right, low, high); return root; } };

详细执行流程解析

我们以示例 1 为例，模拟递归执行过程：输入：root = [1,0,2], low = 1, high = 2

处理根节点1：
- 1在[1,2]区间内，需要修剪其左右子树
- 先递归处理左子树0，再递归处理右子树2
处理左子树节点0：
- 0 < 1，不符合条件，直接返回其右子树（nullptr）
- 根节点的左指针最终指向nullptr
处理右子树节点2：
- 2在[1,2]区间内，修剪其左右子树（均为nullptr，无变化）
- 返回节点2
最终结果：
- 根节点1保留，左子树为空，右子树为2，即[1,null,2]

关键细节与易错点

递归终止条件的位置必须先判断节点是否为空，否则访问root->val会导致空指针异常。
节点值越界的处理逻辑
- 当节点值< low时，只需要递归处理右子树（左子树所有值更小，必然越界）
- 当节点值> high时，只需要递归处理左子树（右子树所有值更大，必然越界）这是利用 BST 性质的核心优化，避免了不必要的递归调用。
根节点的变化当原根节点值不在区间内时，新的根节点会由其左 / 右子树的修剪结果决定，这也是题目中 “根节点可能改变” 的原因。

复杂度分析

时间复杂度：\(O(n)\)，其中 n 为树的节点数。每个节点最多被访问一次。
空间复杂度：\(O(h)\)，其中 h 为树的高度。递归调用栈的深度等于树的高度，最坏情况下（树退化为链表）为 \(O(n)\)。

拓展：迭代版实现（可选）

如果不想使用递归，也可以用迭代的方式实现，分为两步：

先找到新的根节点（值在[low, high]内的第一个节点）
分别修剪新根节点的左、右子树

cpp

class Solution { public: TreeNode* trimBST(TreeNode* root, int low, int high) { if (!root) return nullptr; // 1. 找到新的根节点 while (root && (root->val < low || root->val > high)) { if (root->val < low) root = root->right; else root = root->left; } if (!root) return nullptr; // 2. 修剪左子树 TreeNode* cur = root; while (cur->left) { if (cur->left->val < low) { cur->left = cur->left->right; } else { cur = cur->left; } } // 3. 修剪右子树 cur = root; while (cur->right) { if (cur->right->val > high) { cur->right = cur->right->left; } else { cur = cur->right; } } return root; } };