( “树” 之 BST) 669. 修剪二叉搜索树 ——【Leetcode每日一题】

素颜马尾好姑娘i 2024-03-23 15:13 116阅读 0赞

> 二叉查找树（BST）：根节点大于等于左子树所有节点，小于等于右子树所有节点。  
> 二叉查找树中序遍历有序。

### 669. 修剪二叉搜索树 ###

给你二叉搜索树的根节点 `root` ，同时给定最小边界`low` 和最大边界 `high`。通过修剪二叉搜索树，使得所有节点的值在`[low, high]`中。修剪树 **不应该** 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 **唯一的答案** 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

##### 示例 1： #####

![在这里插入图片描述][bf9826c8e54b41b79ccfad7d63deb948.png]

> 输入：root = \[1,0,2\], low = 1, high = 2  
> 输出：\[1,null,2\]

##### 示例 2： #####

![在这里插入图片描述][814deae038fd4d41ac2743b4537e8129.png]

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

**提示：**

*  树中节点数在范围  \[ 1 , 1 0 4 \] \[1, 10^4\] \[1,104\] 内
 *   0 < = N o d e . v a l < = 1 0 4 0 <= Node.val <= 10^4 0<=Node.val<=104
 *  树中每个节点的值都是 唯一 的
 *  题目数据保证输入是一棵有效的二叉搜索树
 *   0 < = l o w < = h i g h < = 1 0 4 0 <= low <= high <= 10^4 0<=low<=high<=104

#### 思路： ####

**法一：递归：**

任意一个节点的`val`，对给定的范围只有三种可能，**等于**、**小于**、**大于**

1.  **等于**：也就在给定的范围内，则保留，再分别判断该节点的左子树和右子树；
2.  **小于**：当该节点小于给定范围的最小值时，要将该节点以及该节点的左子树都修剪掉，让该节点的父节点的左指针指向该节点的右子树，再进行判断；
3.  **大于**：当该节点大于给定范围的最大值时，要将该节点以及该节点的右子树都修剪掉，让该节点的父节点的右指针指向该节点的左子树，再进行判断；

**法二：迭代：**

该题自然能够使用「迭代」进行求解：起始先从给定的 `root` 进行出发，找到第一个满足值符合 `[low,high]`范围的节点，该节点为最后要返回的真正的根节点 `root`。

然后分别处理`root`节点的左子树和右子树：

*  这里对**左子树**，只需修剪掉**小于**所给范围的节点；
    
     *  若节点大于给定范围的最小值时，这该节点的右子树一定在范围内，不修剪，继续判断其左子树；
     *  若节点小于给定范围的最小值时，要将该节点以及该节点的左子树都修剪掉，让该节点的父节点的左指针指向该节点的右子树，再进行判断。
 *  而对**右子树**只需修剪掉**大于**所给范围的节点;
    
     *  若节点小于给定范围的最大值时，这该节点的左子树一定在范围内，不修剪，继续判断其左子树；
     *  若节点大于给定范围的最大值时，要将该节点以及该节点的右子树都修剪掉，让该节点的父节点的右指针指向该节点的左子树，再进行判断。

#### 代码：(Java、C++) ####

**法一：递归：**  
**Java**

/**
     * 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;
            if(root.val >= low && root.val <= high){
        
                root.left = trimBST(root.left, low, high);
                root.right = trimBST(root.right, low, high);
            }else if(root.val < low){
        
                return trimBST(root.right, low, high);
            }else if(root.val > high){
        
                return trimBST(root.left, low, high);
            }
            return root;
        }
    }

**C++**

/**
     * 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) {
        
            if(root == nullptr) return nullptr;
            if(root->val >= low && root->val <= high){
        
                root->left = trimBST(root->left, low, high);
                root->right = trimBST(root->right, low, high);
            }else if(root->val < low){
        
                return trimBST(root->right, low, high);
            }else if(root->val > high){
        
                return trimBST(root->left, low, high);
            }
            return root;
        }
    };

**法二：迭代：**  
**Java**

class Solution {
        
        public TreeNode trimBST(TreeNode root, int low, int high) {
        
           while(root != null && (root.val < low || root.val > high)){
        
               root = root.val < low ? root.right : root.left;
           }
           if(root == null) return null;
           TreeNode tem = root;
           while(tem.left != null){
        
               if(tem.left.val >= low){
        
                   tem = tem.left;
               }else{
        
                   tem.left = tem.left.right;
               }
           }
           tem = root;
           while(tem.right != null){
        
               if(tem.right.val <= high){
        
                   tem = tem.right;
               }else{
        
                   tem.right = tem.right.left;
               }
           }
           return root;
        }
    }

**C++**

class Solution {
        
    public:
        TreeNode* trimBST(TreeNode* root, int low, int high) {
        
            while(root != nullptr && (root->val < low || root->val > high)){
        
               root = root->val < low ? root->right : root->left;
           }
           if(root == nullptr) return nullptr;
           TreeNode* tem = root;
           while(tem->left != nullptr){
        
               if(tem->left->val >= low){
        
                   tem = tem->left;
               }else{
        
                   tem->left = tem->left->right;
               }
           }
           tem = root;
           while(tem->right != nullptr){
        
               if(tem->right->val <= high){
        
                   tem = tem->right;
               }else{
        
                   tem->right = tem->right->left;
               }
           }
           return root;
        }
    };

##### 运行结果： #####

![在这里插入图片描述][0e701528d8ce462b894b485014869291.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ) O(n) O(n)，其中 `n` 为二叉树的结点数目。
 *  **空间复杂度**： O ( 1 ) O(1) O(1)。迭代只需要常数级空间；而递归的话，递归栈最坏情况下需要  O ( n ) O(n) O(n) 的空间。

题目来源：[力扣。][Link 1]

> 放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！  
> 关注我 [leetCode专栏][leetCode]，每日更新！

##### 注： 如有不足，欢迎指正！ #####

[bf9826c8e54b41b79ccfad7d63deb948.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/95686b1f58954843ad11324a37789e3a.png
[814deae038fd4d41ac2743b4537e8129.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/a5cc5ee2ea0346efbb4dd40595f0e6d1.png
[0e701528d8ce462b894b485014869291.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/2aec7c694b5545a3b3b1680fc4ef5517.png
[Link 1]: https://leetcode.cn/problems/trim-a-binary-search-tree/description/?orderBy=most_votes%3ForderBy%3Dmost_votes%3ForderBy%3Dmost_votes%3ForderBy%3Dmost_votes
[leetCode]: http://t.csdn.cn/kQLJO