代码随想录刷题day23 | 669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树

669. 修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。

示例：

输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]

此题需要注意的是，当节点的值不在[low,high]区间内时，不能直接返回null，这样可能会多剪枝。比如上图示例的节点0，不在[1,3]区间内，但是它的右子树是符合条件的！
所以，
当节点的值小于low时，递归修剪它的右孩子并返回；
当节点的值大于high时，递归修剪它的左孩子并返回。

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root == nullptr) return nullptr;
        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;
    }
};
1
2
3
4
5
6
7
8
9
10
11

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

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

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

示例 ：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]

解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案

题目之所以让我们构造高度平衡的二叉搜索树，是为了防止出现下面的情况（哈哈哈）：

要想让二叉搜索树高度平衡，每次选取数组的中间元素构造根节点（这样左右节点的数量相等），然后递归构造左子树和右子树，最后返回根节点。

class Solution {
public:
    TreeNode* travasal(vector<int>& nums, int left, int right){
        //左闭右闭区间，当left > right时，区间内没有元素，返回null
        if(left > right) return nullptr;
        //每次选取数组的中间节点，然后递归构造左子树和右子树
        int mid = (left + right) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = travasal(nums, left, mid - 1);
        root->right = travasal(nums, mid + 1, right);
        return root; 
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return travasal(nums, 0, nums.size() - 1);//左闭右闭区间
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

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

示例：

二叉搜索树转换为累加树的遍历顺序是右中左，从大到小遍历

class Solution {
public:
    int pre = 0;//记录前一个节点的数值，初始值为0
    void travasal(TreeNode* cur){
        if(cur == nullptr) return;
        travasal(cur->right);//右
        cur->val += pre;//中
        pre = cur->val;
        travasal(cur->left);//左
    }
    TreeNode* convertBST(TreeNode* root) {
        travasal(root);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15