代码随想录-训练营-day18

669. 修剪二叉搜索树 - 力扣（LeetCode）

这个题可以说是为二叉搜索树量身定做的题目，因为二叉搜索树的性质我们可以简单的从左右分辨出值的大小差异，方便我们进行递归或者迭代。比起具体的代码，这个题主要的难点在于如何去理解删除不符合要求的树节点的同时保留二叉搜索树的结构。比如我们发现了一个节点的值小于我们要求的最小值，那么其实我们需要从这个节点的父节点开始操作，比如我们发现父节点的左子树小于当前要求的最小值，那么我们就需要去将我们的左子树替换成左子树自己的右子树（左子树自己的右子树会比左子树本身大），这就是这个题目根本的逻辑，当然，实现这一切的基础是我们需要找到第一个符合范围要求的根节点。

我们先来递归的做法：

/**
 * 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 nullptr;
        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;
    }
};

我们来理清楚这个递归背后的含义，首先我们判断当前节点是否存在，不存在的话就返回空节点。接着我们就判断当前值是否在范围内，如果不在范围内我们就进行递归删除节点并返回这些节点，最后我们遍历所有节点即可。

然后是我们的迭代做法：

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

我比起递归法更喜欢迭代的原因就是迭代的代码中会把思路展现得非常具体，非常具有可读性。所以只有特别简单的或者特别复杂的题我才会选择使用递归，不然迭代法是更易于我们去理解题目的。

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

又是通过数组来构造二叉树的题目，不过这题是要求构造二叉搜索树，具体的要求反而让题目变得容易。因为这个题的数组也是有序的，且二叉搜索树我们只用把小的值放左边大的值放右边，我们可以充分利用二分法的思想：我们先找到数组的中间值，按照性质这个应该就是根节点（父节点），然后不断递归地去寻找左子树和右子树的节点即可。

/**
 * 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* helper(vector<int>& nums,int l,int r){
        if(l>r)return nullptr;
        int mid=l+(r-l)/2;
        TreeNode* root=new TreeNode(nums[mid]);
        root->left=helper(nums,l,mid-1);
        root->right=helper(nums,mid+1,r);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.size()==0)return nullptr;
        return helper(nums,0,nums.size()-1);
    }
};

538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

这个题主要难点在于去理解累加树的概念，具体来说其实就是我们从二叉搜索树进行反向的中序遍历（右子树->根节点->左子树）并且维护住一个累加的值即可。

递归迭代当然都是可以的，因为本质上其实就是在进行反向的中序遍历。

递归：

/**
 * 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:
    int pre=0;
    void helper(TreeNode* cur){
        if(!cur)return;
        helper(cur->right);
        cur->val+=pre;
        pre=cur->val;
        helper(cur->left);
        return;
    }
    TreeNode* convertBST(TreeNode* root) {
        if(!root)return nullptr;
        helper(root);
        return root;
    }
};

迭代：

/**
 * 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:
    int pre=0;
    TreeNode* helper(TreeNode* root){
        if(!root)return nullptr;
        stack<TreeNode*> stk;
        TreeNode* cur=root;
        while(!stk.empty()||cur){
            while(cur){
                stk.push(cur);
                cur=cur->right;
            }
            cur=stk.top();
            stk.pop();
            cur->val+=pre;
            pre=cur->val;
            cur=cur->left;
        }
        return root;
    }
    TreeNode* convertBST(TreeNode* root) {
        if(!root)return nullptr;
        return helper(root);
    }
};