【LeetCode二叉树#18】修剪二叉搜索树（涉及重构二叉树与递归回溯）

修剪二叉搜索树

力扣题目链接(opens new window)

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

思路

题目描述得有点唬人，其实意思就是给一个区间范围（比如[2, 7]），然后要求你把节点值不在这个范围内的节点给删除掉，并且之后还是二叉搜索树

一种经典的错误思路是：遇到不符合区间的节点时，直接返回NULL给上一个节点

这样做的话，如果不满足条件的节点的子树还有满足条件的值的话，也会被舍弃，从而出错

当我们找到一个不在规定范围内的节点时，首先要判断它是小于范围还是大于范围

如果节点（假设为A）的值小于规定范围，根据二叉搜索树的性质，其右子树有可能还存在满足规定范围的节点，因此需要继续遍历其右子树

如果节点（假设为A）的值大于规定范围，根据二叉搜索树的性质，其左子树有可能还存在满足规定范围的节点，因此需要继续遍历其左子树

基本思路是这样的

下面来看代码

代码

还是使用递归法来做

1、确定递归函数的参数和返回值

参数肯定是根节点啦，因为我们需要修改二叉树，所以修改的新值需要层层传递到上层递归的调用处，因此需要返回值

那么可以直接用解题模板

class Solution {
public:
    //确定递归函数的参数和返回值
    TreeNode* trimBST(TreeNode* root, int low, int high) {

    }
};

2、确定终止条件

如果当前输入的节点为空，那么应该返回空并结束递归

class Solution {
public:
    //确定递归函数的参数和返回值
    TreeNode* trimBST(TreeNode* root, int low, int high) {
		//确定终止条件
        if(root == NULL) return NULL;
    }
};

3、确定单层处理逻辑

当前节点小于规定范围时，遍历其右子树

class Solution {
public:
    //确定递归函数的参数和返回值
    TreeNode* trimBST(TreeNode* root, int low, int high) {
		//确定终止条件
        if(root == NULL) return NULL;
        
        //确定单层递归逻辑
        if(root->val < low){//遍历其右子树
            TreeNode* right = trimBST(root->right, low, high);
            return right;
        }
    }
};

解释一下递归右子树的代码的含义

上面那样写的意思是：使用当前节点作为根节点，递归遍历其右子树，最后返回一颗经过修剪的满足条件的右子树

实在不理解或者忘了，可以自己模拟一下过程

同理，当前节点大于规定范围时，遍历其左子树

class Solution {
public:
    //确定递归函数的参数和返回值
    TreeNode* trimBST(TreeNode* root, int low, int high) {
		//确定终止条件
        if(root == NULL) return NULL;
        
        //确定单层递归逻辑
        if(root->val < low){//遍历其右子树
            TreeNode* right = trimBST(root->right, low, high);
            return right;
        }
        
        if(root->val > high){//遍历其左子树
            TreeNode* left = trimBST(root->left, low, high);
            return left;
        }
        //调用递归，把修剪后的左子树或右子树返回
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;
        
    }
};

注意，这里我们要搜索的是当前节点的左子树或右子树（是整颗树）

还是模拟一下过程把怕之后看又不记得了

首先我们将根节点输入到递归函数中，此时其不满足递归结束的条件，假设其值也在规定范围内

那么此时会调用递归，去遍历根节点的左右子树【第一层递归，希望返回的是一颗修剪后的左或右子树】

然后进入左子树，若当前左子树的根节点不在规定范围内，则触发对应的单层处理逻辑

假设此时触发的是root->val < low条件，那么回去递归遍历当前左子树根节点的右子树【第二层递归，希望返回的是一颗修剪后的右子树】

假设其右子树均满足规定范围，那么当递归遍历到叶子节点后，会触发终止条件，然后每层递归都往上返回自己的结果，从而得到修改后的树