Day25:Leetcode：669. 修剪二叉搜索树 + 108.将有序数组转换为二叉搜索树 + 538.把二叉搜索树转换为累加树

LeetCode：669. 修剪二叉搜索树

问题描述

解决方案：

1.思路

2.代码实现

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        if (root.val < low) {
            return trimBST(root.right, low, high);
        } else if (root.val > high) {
            return trimBST(root.left, low, high);
        } else {
            root.left = trimBST(root.left, low, high);
            root.right = trimBST(root.right, low, high);
            return root;
        }
    }
}

3.复杂度分析

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

问题描述

解决方案：

1.思路：

• 考虑到是构建高度平衡的搜索二叉树，所以可以总是选择中间位置左边的数字作为根节点；

2.代码实现

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    public TreeNode helper(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        // 总是选择中间位置左边的数字作为根节点
        int mid = (left + right) / 2;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid - 1);
        root.right = helper(nums, mid + 1, right);
        return root;
    }
}

3.复杂度分析

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

问题描述

解决方案：

1.思路：

2.代码实现

public TreeNode convertBST(TreeNode root) {
    if (root != null) {
        convertBST(root.right);
        sum += root.val;
        root.val = sum;
        convertBST(root.left);
    }
    return root;
}

3.复杂度分析