【LeetCode】No.108. Convert Sorted Array to Binary Search Tree -- Java Version

题目链接：https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/

1. 题目介绍（Convert Sorted Array to Binary Search Tree）

Given an integer array nums where the elements are sorted in ascending order, convert it to a
height-balanced binary search tree.

【Translate】： 给定一个整数数组nums，其中元素按升序排序，将其转换为高度平衡的二叉搜索树。

【测试用例】：

示例1：

示例2：

【条件约束】：

【相似问题】：

2. 题解

2.1 递归

原题解来自于 ganajayant 的 ✅Java Solution || Recursion || 0ms 100% Faster 🔥🔥🔥 || Beginner Friendly.

该题用递归来进行解题，显得轻松又愉快，下面是两个可能会产生疑问的点：

Q1：为什么nums[mid]会成为根节点 ？
A1：这是因为题目要求我们构建的是一个高度平衡的二叉搜索树，我们在保证左右大小的同时，还要确保高度平衡，如果我们从中间开始，就会有相同数量的元素分别插入到左边和右边。而且该题给我们的是一个升序排列的数组，这也在一定程度上降低了题目的难度。

Q2：为什么 mid 更倾向于 = left+(right-left)/2 ？
A2：为了防止数据溢出。这个问题在较小的数值中是不会出现任何问题的，而在 left+right > Integer.MAX_VALUE 时，就会发生数据溢出，而如果采用left+(right-left)/2，(right - left) 是从一个较大的数字中减去一个较小的数字，就会产生一个更小的数字，这样它就很难再数据溢出。而在本题中，条件约束限定了范围，已经确定了它不会产生数据溢出，所以使用哪一种写法均可。在理论上，二者是相等的，两个值都等于 left + (right - left)/2 = (2*left + right - left)/2 = (left + right)/2。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return creatBTS(nums, 0, nums.length-1);
    }

    private TreeNode creatBTS(int[] nums, int left, int right){
        if(left > right) return null;

        int mid = left + (right-left)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = creatBTS(nums, left, mid-1);
        root.right = creatBTS(nums, mid+1, right);

        return root;
    }
}
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

3. 参考资料

[1] 数据结构——二叉排序树（Java代码实现）| CSDN
[2] why left+(right-left)/2 will not overflow? | StackOverflow