(二刷）代码随想录第23天|538.把二叉搜索树转换为累加树 669. 修剪二叉搜索树 108.将有序数组转换为二叉搜索树

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

观察实例可以看出二叉树的遍历顺序为右中左:

递归三部曲：

class Solution {
    // 将 sum 定义为类的成员变量
    int sum;
    
    public TreeNode convertBST(TreeNode root) {
        sum = 0;  // 初始化 sum 为 0
        convertBST1(root);
        return root;        
    }

    // 按右中左顺序遍历，累加即可
    public void convertBST1(TreeNode root) {
        // 确定终止条件
        if (root == null) return;
        // 递归转换右子树
        convertBST1(root.right);
        // 将当前节点的值加到 sum 中
        sum += root.val;
        // 将累加后的值更新到当前节点
        root.val = sum;
        // 递归转换左子树
        convertBST1(root.left);
    }
}

// 定义二叉树的节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int x) {
        val = x;
    }
}

669. 修剪二叉搜索树 

// 定义一个类Solution
class Solution {
    // 定义一个方法trimBST，接受三个参数：树的根节点root，和范围的上下界low和high
    public TreeNode trimBST(TreeNode root, int low, int high) {
        // 如果根节点为空，直接返回空
        if (root == null) {
            return null;
        }
        // 如果根节点的值小于low，说明根节点和它的左子树都不在范围内
        // 所以需要在右子树中继续修剪
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }
        // 如果根节点的值大于high，说明根节点和它的右子树都不在范围内
        // 所以需要在左子树中继续修剪
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }
        // 如果根节点的值在[low, high]范围内
        // 对左子树进行修剪，并将修剪后的左子树连接到根节点的左子节点
        root.left = trimBST(root.left, low, high);
        // 对右子树进行修剪，并将修剪后的右子树连接到根节点的右子节点
        root.right = trimBST(root.right, low, high);
        // 返回修剪后的根节点
        return root;
    }
}

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

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

// 定义一个类Solution
class Solution {
    // 定义一个方法sortedArrayToBST，接受一个排序数组nums作为参数
    public TreeNode sortedArrayToBST(int[] nums) {
        // 调用重载的sortedArrayToBST方法，将整个数组范围传递进去
        return sortedArrayToBST(nums, 0, nums.length);
    }
    
    // 定义一个重载的sortedArrayToBST方法，接受一个排序数组nums，以及数组的左右边界left和right
    public TreeNode sortedArrayToBST(int[] nums, int left, int right) {
        // 如果左边界大于或等于右边界，说明当前子数组为空，返回null
        if (left >= right) {
            return null;
        }
        // 如果当前子数组只有一个元素，直接将这个元素作为节点返回
        if (right - left == 1) {
            return new TreeNode(nums[left]);
        }
        // 计算当前子数组的中间位置
        int mid = left + (right - left) / 2;
        // 创建一个新节点，值为中间位置的元素
        TreeNode root = new TreeNode(nums[mid]);
        // 递归构建左子树，范围为[left, mid)
        root.left = sortedArrayToBST(nums, left, mid);
        // 递归构建右子树，范围为(mid, right)
        root.right = sortedArrayToBST(nums, mid + 1, right);
        // 返回当前节点作为根节点
        return root;
    }
}