代码随想录算法训练营Day21 | 669. 修剪二叉搜索树 | 108.将有序数组转换为二叉搜索树 | 538.把二叉搜索树转换为累加树

今日任务

669. 修剪二叉搜索树

• 题目链接： https://leetcode.cn/problems/trim-a-binary-search-tree/description/
• 题目描述：
  

Code

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root == nullptr){
            return root;
        }
        if(root->val < low){
            return trimBST(root->right, low, 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;
    }
};

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

• 题目链接： https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/
• 题目描述：
  

Code

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {

        function<TreeNode *(int , int)> dfs = [&](int low, int high) -> TreeNode *{
            if(low > high){
                return nullptr;
            }
            int mid = low + (high - low) / 2;
            TreeNode *left = dfs(low, mid - 1);
            TreeNode *right = dfs(mid + 1, high);
            return new TreeNode(nums[mid], left, right);
        };
        return dfs(0, nums.size() - 1);
    }
};

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

• 题目链接： https://leetcode.cn/problems/convert-bst-to-greater-tree/description/
• 题目描述：
  

Code

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        int sum = 0;
        function<void(TreeNode *)> dfs = [&](auto node)->void{
            if(node == nullptr){
                return;
            }
            dfs(node->right);
            sum += node->val;
            node->val = sum;
            dfs(node->left);
        };
        dfs(root);
        return root;
    }
};