算法刷题 Day 23 | 669. 修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树

今日内容：

• 修剪二叉搜索树
• 将有序数组转换为二叉搜索树
• 把二叉搜索树转换为累加树
• 总结篇

详细布置

669. 修剪二叉搜索树

这道题目比较难，比 添加增加和删除节点难的多，建议先看视频理解。

题目链接/文章讲解： https://programmercarl.com/0669.%E4%BF%AE%E5%89%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

视频讲解： https://www.bilibili.com/video/BV17P41177ud

Tips：这道题目要注意，不是简单的去掉不满足条件的子节点就可以，因为子节点的左右子树当中可能还有满足条件的节点。因此，当遇到不满足条件的节点时，还是要遍历其可能满足条件的左右子节点，并通过返回满足条件的节点的方式来替代原节点。如图所示：

我的题解：

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;
    }
};

108.将有序数组转换为二叉搜索树

本题就简单一些，可以尝试先自己做做。

https://programmercarl.com/0108.%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

视频讲解：https://www.bilibili.com/video/BV1uR4y1X7qL

Tips：这道题相对来说还比较简单，以数组中间元素为根节点，然后不断左右递归建树即可。

我的题解：

class Solution {
public:
    TreeNode* traversal(vector<int>& nums, int begin, int end){
        if(begin >= end){
            return NULL;
        }

        int middle = begin + (end - begin) /2;
        TreeNode* root = new TreeNode(nums[middle]);
        root->left = traversal(nums, begin, middle);
        root->right = traversal(nums, middle+1, end);
        return root;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return traversal(nums, 0, nums.size());
    }
};

538.把二叉搜索树转换为累加树

本题也不难，在 求二叉搜索树的最小绝对差 和 众数 那两道题目 都讲过了 双指针法，思路是一样的。

https://programmercarl.com/0538.%E6%8A%8A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E8%BD%AC%E6%8D%A2%E4%B8%BA%E7%B4%AF%E5%8A%A0%E6%A0%91.html

视频讲解：https://www.bilibili.com/video/BV1d44y1f7wP

Tips：这道题也很简单，遍历顺序按照右中左来即可，并定义一个全局变量用于累加。

我的题解：

class Solution {
public:
    int sum = 0;
    void traversal(TreeNode* root){
        if(root == NULL){
            return;
        }
        
        traversal(root->right);
        sum += root->val;
        root->val = sum; 
        traversal(root->left);
        return;
    }
    
    TreeNode* convertBST(TreeNode* root) {
        traversal(root);
        return root;
    }
};

总结篇

好了，二叉树大家就这样刷完了，做一个总结吧

https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E6%80%BB%E7%BB%93%E7%AF%87.html