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 .

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,null,3] and [3,1] They're all highly balanced binary search trees .

reflection

Build a search Binary Tree Based on an ordered array ,

Because arrays are ordered , So we keep selecting arrays every time ( This array is not the same as the previous array , Is the array after cutting ) Take the middle number of as the root node

Initialize first

• Get the coordinates in the middle of the array as rootIndex

• Get the value in the middle of the array as rootval

• Create a root node

• Initialize the left and right boundaries as left,right

Recursion

• If left==right Represents the end of recursion

• If left≠rootindex , Prove that the node has a left child , Build its left child , And cut the array to continue recursion

• If right≠rootindex , Prove that the node has a right child , Build its right child , And cut the array to continue recursion

The roughly incomplete process is shown in the figure

public static TreeNode sortedArrayToBST(int[] nums) {
    
        if(nums.length==1) return new TreeNode(nums[0]);
        int rootindex = nums.length/2;
        int rootval = nums[rootindex];
        TreeNode root = new TreeNode(rootval);
        // left and right representative root Boundary of subtree 
        // left Represents the left border 
        // right Represents the right border 
        int left = 0;
        int right = nums.length-1;
        AddNode(root,nums,left,right,rootindex);
        return root;
    }

    private static void AddNode(TreeNode root, int[] nums, int left, int right, int rootIndex) {
    
        //  Recursion end condition 
        if(left==right) return;
        //  The node has a left subtree 
        if(left!=rootIndex){
    
            int rootLeftIndex = (rootIndex-left)/2+left;
            TreeNode rootleft= new TreeNode(nums[rootLeftIndex]);
            root.left=rootleft;
            // Next, continue to build its left and right subtrees for this node 
            AddNode(rootleft,nums,left,rootIndex-1,rootLeftIndex);
        }
        //  The node has a right subtree 
        if(right!=rootIndex){
    
            int rootRightIndex = (right + 1 - rootIndex)/2 + rootIndex;
            TreeNode  rootright=new TreeNode(nums[rootRightIndex]);
            root.right=rootright;
            // Next, continue to build its left and right subtrees for this node 
            AddNode(rootright,nums,rootIndex+1,right,rootRightIndex);
        }
    }