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

刷题笔记day23

669.修剪二叉搜索树目

文章讲解：代码随想录
是否自己做出来通过全部用例：否

遇到的困难/犯的错误

想用删除二叉搜索树的解法，每次删除一个节点，但是失败了。

自己写的代码

题解方法：

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

看了题解后的收获

这题一个函数里面套了四个函数，比较绕，但还是能理解。

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

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

先看了题解，思路：选中间节点不断切割左右，是中序+后序确定一颗二叉树的退阶版本。

自己写的代码

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

看了题解后的收获

不断中间分割，然后递归处理左区间，右区间，也可以说是分治。

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

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

先看了题解，右中左遍历。

自己写的代码

class Solution {
public:
    TreeNode* pre = NULL;
    TreeNode* convbst(TreeNode* node) {
        if (!node) return NULL;
        node->right = convbst(node->right);
        if (pre) node->val += pre->val;
        pre = node;
        node->left = convbst(node->left);
        return node;
    }
    TreeNode* convertBST(TreeNode* root) {
        return convbst(root);
    }
};

看了题解后的收获

这题是反中序遍历，比较简单。