Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree

산수적인 직관이 중요한데 이걸 잘 못하는거 같다.

start, end 처리를 계산하는데 몇 십 분을 썻는지 모르겠다.

center = start + Math.round((start - end - 1) / 2) -1

var sortedArrayToBST = function(nums,start=0,end=nums.length-1) {
    if(end < start) return null;
    if(start == end) return new TreeNode(nums[start]);
    
    let center = start + Math.round((end - start + 1) / 2) - 1;
    let centerNode = new TreeNode(nums[center]);
    
    centerNode.left = sortedArrayToBST(nums,start, center-1);
    centerNode.right = sortedArrayToBST(nums, center+1, end);
    
    return centerNode;
};

이렇게 했는데 사실 의미 없는게 Binary Search에서 많이 사용하는

center = left + Math.floor((right - left)/2)

이거 말고

center = left + right / 2

도 있는데 overflow 때문에 잘 안쓴다고 한다.

를 사용하면 되는 거였다.

var sortedArrayToBST = function(nums,start=0,end=nums.length-1) {
    if(end < start) return null;
    if(start == end) return new TreeNode(nums[start]);
    
    //let center = start + Math.round((end - start + 1) / 2) - 1;
    let center = Math.floor(start + (end - start)/ 2);
    let centerNode = new TreeNode(nums[center]);
    
    centerNode.left = sortedArrayToBST(nums,start, center-1);
    centerNode.right = sortedArrayToBST(nums, center+1, end);
    
    return centerNode;
};