Recursive method converts ordered array into binary search tree

108. Convert an ordered array to a binary search tree

The difficulty is simple

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 .

Ideas

The title says that it should be converted into a highly balanced binary search tree . What's the difference between this and converting to an ordinary binary search tree ？

If it is balanced, we will naturally think of dividing the array from the middle of the array , Take the intermediate element as the root node , Use the left node to construct the left subtree , Use the nodes on the right to construct the right subtree , Then recursively construct the elements on the left and right , Until the interval length is 0 until .

This is very similar to dichotomy , Half and half treatment .

Then you need to pay attention to the scope you define , It is suggested to uniformly use the form of left closed right open or both left and right closed in your own coding , Don't switch between the two , It's easy to get dizzy

package cn.edu.xjtu.carlWay.tree.array2BST;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

/** * 108.  Convert an ordered array to a binary search tree  *  Give you an array of integers  nums , Where elements have been   Ascending   array , Please turn it into a   Highly balanced   Binary search tree . * <p> *  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 . * <p> * https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/ */
public class Solution {
    
    public TreeNode sortedArrayToBST(int[] nums) {
    
        return helpBuild(nums, 0, nums.length);
    }

    //  The range here is left closed and right open , It's especially necessary to understand this 
    private TreeNode helpBuild(int[] nums, int left, int right) {
    
        if (left == right) {
    
            return null;
        }
        if (right - left == 1) {
    
            return new TreeNode(nums[left]);
        }
        //  Find the middle root node 
        int idx = left + (right - left) / 2;
        TreeNode node = new TreeNode(nums[idx]);
        //  Construct the left subtree 
        node.left = helpBuild(nums, left, idx);
        //  Construct the right subtree 
        node.right = helpBuild(nums, idx + 1, right);
        return node;
    }
}