题目描述给你二叉搜索树的根节点root同时给定最小边界low和最大边界high。通过修剪二叉搜索树使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构即如果没有被移除原有的父子代关系都应当保留可以证明存在唯一的答案结果应当返回修剪好的二叉搜索树的新的根节点根节点可能会根据给定的边界发生改变核心思路利用二叉搜索树的性质递归修剪二叉搜索树BST的核心性质左子树所有节点值 根节点值右子树所有节点值 根节点值中序遍历结果为升序序列基于这个性质我们可以用递归的方式对每个节点进行判断和修剪如果当前节点为空直接返回空递归终止条件如果当前节点值 low说明当前节点和其左子树都不符合条件直接返回右子树的修剪结果如果当前节点值 high说明当前节点和其右子树都不符合条件直接返回左子树的修剪结果如果当前节点值在[low, high]区间内递归修剪其左、右子树最后返回当前节点完整代码实现Ccpp/** * 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处理根节点11在[1,2]区间内需要修剪其左右子树先递归处理左子树0再递归处理右子树2处理左子树节点00 1不符合条件直接返回其右子树nullptr根节点的左指针最终指向nullptr处理右子树节点22在[1,2]区间内修剪其左右子树均为nullptr无变化返回节点2最终结果根节点1保留左子树为空右子树为2即[1,null,2]关键细节与易错点递归终止条件的位置必须先判断节点是否为空否则访问root-val会导致空指针异常。节点值越界的处理逻辑当节点值 low时只需要递归处理右子树左子树所有值更小必然越界当节点值 high时只需要递归处理左子树右子树所有值更大必然越界这是利用 BST 性质的核心优化避免了不必要的递归调用。根节点的变化当原根节点值不在区间内时新的根节点会由其左 / 右子树的修剪结果决定这也是题目中 “根节点可能改变” 的原因。复杂度分析时间复杂度\(O(n)\)其中 n 为树的节点数。每个节点最多被访问一次。空间复杂度\(O(h)\)其中 h 为树的高度。递归调用栈的深度等于树的高度最坏情况下树退化为链表为 \(O(n)\)。拓展迭代版实现可选如果不想使用递归也可以用迭代的方式实现分为两步先找到新的根节点值在[low, high]内的第一个节点分别修剪新根节点的左、右子树cppclass 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; } };总结修剪二叉搜索树的核心就是利用 BST 的有序性通过递归快速定位需要保留的节点整个过程不需要额外空间仅通过修改指针就能完成修剪同时保证了原有的父子关系不变。
今日算法（二叉树剪枝）
题目描述给你二叉搜索树的根节点root同时给定最小边界low和最大边界high。通过修剪二叉搜索树使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构即如果没有被移除原有的父子代关系都应当保留可以证明存在唯一的答案结果应当返回修剪好的二叉搜索树的新的根节点根节点可能会根据给定的边界发生改变核心思路利用二叉搜索树的性质递归修剪二叉搜索树BST的核心性质左子树所有节点值 根节点值右子树所有节点值 根节点值中序遍历结果为升序序列基于这个性质我们可以用递归的方式对每个节点进行判断和修剪如果当前节点为空直接返回空递归终止条件如果当前节点值 low说明当前节点和其左子树都不符合条件直接返回右子树的修剪结果如果当前节点值 high说明当前节点和其右子树都不符合条件直接返回左子树的修剪结果如果当前节点值在[low, high]区间内递归修剪其左、右子树最后返回当前节点完整代码实现Ccpp/** * 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处理根节点11在[1,2]区间内需要修剪其左右子树先递归处理左子树0再递归处理右子树2处理左子树节点00 1不符合条件直接返回其右子树nullptr根节点的左指针最终指向nullptr处理右子树节点22在[1,2]区间内修剪其左右子树均为nullptr无变化返回节点2最终结果根节点1保留左子树为空右子树为2即[1,null,2]关键细节与易错点递归终止条件的位置必须先判断节点是否为空否则访问root-val会导致空指针异常。节点值越界的处理逻辑当节点值 low时只需要递归处理右子树左子树所有值更小必然越界当节点值 high时只需要递归处理左子树右子树所有值更大必然越界这是利用 BST 性质的核心优化避免了不必要的递归调用。根节点的变化当原根节点值不在区间内时新的根节点会由其左 / 右子树的修剪结果决定这也是题目中 “根节点可能改变” 的原因。复杂度分析时间复杂度\(O(n)\)其中 n 为树的节点数。每个节点最多被访问一次。空间复杂度\(O(h)\)其中 h 为树的高度。递归调用栈的深度等于树的高度最坏情况下树退化为链表为 \(O(n)\)。拓展迭代版实现可选如果不想使用递归也可以用迭代的方式实现分为两步先找到新的根节点值在[low, high]内的第一个节点分别修剪新根节点的左、右子树cppclass 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; } };总结修剪二叉搜索树的核心就是利用 BST 的有序性通过递归快速定位需要保留的节点整个过程不需要额外空间仅通过修改指针就能完成修剪同时保证了原有的父子关系不变。
