Leetcode 108 converts an ordered array into a binary search tree -- recursive method

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree

---

The question ：

Give you an array of integers nums , Where elements have been Ascending array , Please turn it into a Highly balanced Binary search tree .

Highly balanced A binary tree is a tree that satisfies 「 The absolute value of the height difference between the left and right subtrees of each node does not exceed 1 」 Two fork tree .

Example 1：

Input ：nums = [-10,-3,0,5,9]
Output ：[0,-3,9,-10,null,5]
explain ：[0,-10,5,null,-3,null,9] Will also be considered the right answer ：

Example 2：

Input ：nums = [1,3]
Output ：[3,1]
explain ：[1,3] and [3,1] They're all highly balanced binary search trees .

Tips ：
1 <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums Press Strictly increasing Sequential arrangement

---

Reference article

Ideas ：

I'll finish this problem recursively .

In recursion , If it involves the deletion or addition of binary tree nodes , Then the way of returning nodes using recursive methods can make it more convenient and the code more concise . Because this problem involves the construction of binary tree , That is, the increase of nodes , Therefore, we also use recursive methods to return nodes .

Because the input data given by the topic has been arranged in order , In that case , You're welcome , Directly select the middle value in the current array in each recursive method , The tree constructed in this way is naturally a specific tree in line with high balance . For the cutting of arrays , Not every time new The operation of an array , But use Each time a recursive method is called, the left and right subscripts are passed in The way to achieve .

Note that in this question is used Left and right closed The range of , That is, the nodes of the left and right subscripts of the range are reachable .

What's more, we need to pay attention to , When I first took the position of the middle element of the array, I wrote
int mid = (left + right) >> 1;
Although this problem can pass , But this way of writing , If left and right Values are greater than int Half the maximum , Operation will Transboundary ,mid What you get is a negative number ！ So it should be written like this ：
int mid = left + ((right - left) / 2);

This topic Java Code ：

class Solution {
    
    private TreeNode construct(int[] nums, int left, int right) {
    
        if (left > right) return null;
        int mid = left + ((right - left) / 2);
        TreeNode node = new TreeNode(nums[mid]);
        node.left = construct(nums, left, mid - 1);
        node.right = construct(nums, mid + 1, right);
        return node;
    }

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