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

2024-01-10 06:39:48

669. 修剪二叉搜索树

题目链接:669. 修剪二叉搜索树
文档链接:669. 修剪二叉搜索树
视频链接:你修剪的方式不对,我来给你纠正一下!| LeetCode:669. 修剪二叉搜索树

C++实现

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root == NULL) return NULL;
        if(root->val < low){
            TreeNode* node = trimBST(root->right, low, high);
            return node;
        }
        if(root->val > high){
            TreeNode* node = trimBST(root->left, low, high);
            return node;
        }
        root->left = trimBST(root->left, low, high);
        root->right =trimBST(root->right, low, high);
        return root;
    }
};

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

题目链接:108.将有序数组转换为二叉搜索树
文档链接:108.将有序数组转换为二叉搜索树
视频链接:108.将有序数组转换为二叉搜索树

C++实现

class Solution {
public:
    TreeNode* buildBST(vector<int>& nums, int left, int right){
        if(left >= right) return NULL;
        int mid = left + (right - left)/2;
        int val = nums[mid];
        TreeNode* node = new TreeNode(val);
        node->left = buildBST(nums, left, mid);
        node->right = buildBST(nums, mid+1, right);
        return node;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return buildBST(nums, 0, nums.size());
    }
};

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

题目链接:538.把二叉搜索树转换为累加树
文档链接:538.把二叉搜索树转换为累加树
视频链接:普大喜奔!二叉树章节已全部更完啦!| LeetCode:538.把二叉搜索树转换为累加树

C++实现

class Solution {
private:
    int count = 0;
    void traversal(TreeNode* cur){
        if(cur == NULL) return;
        traversal(cur->right);
        cur->val += count;
        count = cur->val;
        traversal(cur->left);
    }

public:
    TreeNode* convertBST(TreeNode* root) {
        if(root == NULL) return root;
        count = 0;
        traversal(root);
        return root;
    }
};

文章来源:https://blog.csdn.net/Magical_Jasen/article/details/135396836
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。