110、【树与二叉树】leetcode ——669. 修剪二叉搜索树：递归法（C++版本）

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

题目描述

在这里插入图片描述

解题思路

大题思路类似于 450.删除二叉搜索树中的节点递归法+迭代法区别在于删除的是某一区域的节点值并且要保留区域内部的节点值。
对于第一次找到结点值小于low的情况有两种1该结点无右子树那么直接删除这个结点及以下的子树即可返回NULL2该结点有右子树那么右子树中可能有大于low的情况需要继续向右遍历。

同理对于第一次找到结点值大于high的情况也有两种1该结点无左子树那么直接删除这个结点及以下的子树即可返回NULL2该结点有左子树那么左子树中可能有小于high的情况需要继续向左遍历。

本题的关键是用好递归这个结构用好每次他向下的遍历和返回的值。

/**
 * 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)                   return NULL;
        // 当找到的结点值小于low时继续向右遍历保留大于low的删除小于low的
        if(root->val < low)         return trimBST(root->right, low, high);
        // 当找到的结点值大于high时继续向左遍历保留小于high的删除大于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;
    }
};