Gidhub BE Developer

LeetCode : 108. Convert Sorted Array to Binary Search Tree

2020-11-18
goodGid

108. Convert Sorted Array to Binary Search Tree

Problem

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

Code (20. 11. 18)

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

private TreeNode makeBST(int[] nums, int left, int right) {
    if (left > right) {
        return null;
    }

    int centerIdx = left + (right - left) / 2; // [1]
    // int centerIdx = (left + right) / 2;
    // = int centerIdx = (left + right) >> 1;

    TreeNode treeNode = new TreeNode(nums[centerIdx]);
    treeNode.left = makeBST(nums, left, centerIdx - 1);
    treeNode.right = makeBST(nums, centerIdx + 1, right);
    return treeNode;
}
  • [1] : (left + right) / 2 로 할 수 있지만

    이러면 overflow가 발생할 수 있다.

    그러므로 left + (right - left) / 2 로 하는게 조금 더 안전하다.


Reference


Comments

Index