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

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

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

1
2
3
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

Solution：中序遍历

相当于是根据中序遍历来还原平衡二叉搜索树,有点类似于二分查找和创建二叉树的结合，也就是利用二分查找来查找树以及其子树的根节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    // 主方法，接收一个排序的数组，并返回一个高度平衡的二叉搜索树的根节点。
    public TreeNode sortedArrayToBST(int[] nums) {
        // 调用辅助方法 helper，传入数组及其起始和结束索引。
        return helper(nums, 0, nums.length - 1);
    }

    // 辅助递归方法，用于构建子树。接收数组和子数组的左右边界索引。
    public TreeNode helper(int[] nums, int left, int right) {
        // 递归终止条件：如果左边界大于右边界，意味着子数组为空，返回 null。
        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;
    }
}