Convert Sorted Array to BST with explanation


  • 0
    V

    Basic idea is that, first we find the middle one from num[ ] to be the root, and return the root, then separate num[ ] to left[0].....left[middle - 1] and right[middle + 1].....right[ num.length - 1].

    Then root.left will be the return node from sortedArrayToBST(left), root.right will be the return node from sortedArrayToBST(right).

    We continue perform this process until there is no array to split.
    (len - len/2 -1) is different from (len/2 - 1)

    public class Solution {

    public TreeNode sortedArrayToBST(int[] num) {
        
        if(num == null || num.length == 0){
            return null;
        }
        
        if(num.length == 1){
            return new TreeNode(num[0]);
        }
        
        int len = num.length;
        TreeNode root = new TreeNode(num[len/2]);
        
        int[] leftArray = new int[len/2];
        int[] rightArray = new int[len-len/2-1];
        
        
        for(int i = 0; i < leftArray.length; i++){
            leftArray[i] = num[i];
        }
        for(int j = 0; j < rightArray.length; j++){          
            rightArray[j] = num[j+len/2+1];
        }
        
    
        root.left = sortedArrayToBST(leftArray);      
        root.right = sortedArrayToBST(rightArray);
            
        return root;
        
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.