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

669. 修剪二叉搜索树

题目链接：669. 修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

文章讲解/视频讲解：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

思路

自己的实现方法有点稀里糊涂，调了几次bug后通过了。采用后序遍历，在每一次的递归遍历中，首先保存下已经处理过的左右子树。如果当前节点在$][low,high]$范围内，则返回当前节点，如果小于$low$，则返回右子树，如果大于$high$，则返回左子树。

ps：题目好像不能让我们把修剪的节点delete掉，会报错。

C++实现

class Solution {
public:
    TreeNode* traversal(TreeNode* node, int low, int high){
        if(!node) return nullptr;

        TreeNode* left = trimBST(node->left, low, high);
        TreeNode* right = trimBST(node->right, low, high);

        if(node->val >= low && node->val <= high){
            node->left = left;
            node->right = right;
            return node;
        }
        else if(node->val < low){
            return right;
        }
        else{
            return left;
        }
    }

    TreeNode* trimBST(TreeNode* root, int low, int high) {
        TreeNode* result = traversal(root, low, high);
        return result;
    }
};

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

题目链接：108.将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

文章讲解/视频讲解：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

思路

采用递归的方法来实现。因为题目给的是排好序的数组，且要求是一棵高度平衡的二叉搜索树，所以在每次递归的时候，找出当前范围$[left,high]$内的中位数$mid$，以该中位数作为当前子树的头节点，并递归地用$[left,mid?1]$范围内的数组建立左子树，$[mid+1,right]$范围内的数组建立右子树。

C++实现

class Solution {
public:
    TreeNode* traversal(const vector<int>& nums, int left, int right){
        if(left > right) return nullptr;
        int mid = left + (right - left) / 2;
        TreeNode* node = new TreeNode(nums[mid]);
        node->left = traversal(nums, left, mid - 1);
        node->right = traversal(nums, mid + 1, right);
        return node;
    }

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

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

题目链接：538.把二叉搜索树转换为累加树

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

• 节点的左子树仅包含键 小于 节点键的节点。
• 节点的右子树仅包含键 大于 节点键的节点。
• 左右子树也必须是二叉搜索树。

文章讲解/视频讲解：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

思路

采用一种右中左的反向中序遍历，注意，这里与通常的左中右的遍历不同。在反向中序遍历的过程中，记录下前一个遍历到的节点pre，将当前节点node的值加上pre节点的值。

类似地，如果想要求这样的累加树：每个节点node的新值等于原树种小于或等于node.val的值之和，可以采用正向的中序遍历来解决。

C++实现

class Solution {
public:
    TreeNode* pre = nullptr;

    void traversal(TreeNode* node){
        if(!node) return;
        traversal(node->right);
        if(pre) node->val += pre->val;
        pre = node;
        traversal(node->left);
    }

    TreeNode* convertBST(TreeNode* root) {
        traversal(root);
        return root;
    }
};

小结

二叉树的部分终于刷完了，撒花~后面还需要仔细回顾一下。