문제로

못풀었다.

정답

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums == null || nums.length == 0) {
            return null;
        }

        return convertToBST(nums, 0, nums.length -1);
    }

    public TreeNode convertToBST(int[] nums, int left, int right) {
        if(left > right) { // 종료됬음을 의미
            return null;
        }

        int mid = left + (right - left) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = convertToBST(nums, left, mid-1);
        node.right = convertToBST(nums, mid+1, right);

        return node;
    }
}

참고

1

int mid = left + (right - left) / 2;

정수 오버플로우를 방지하기 위해서 위와 같은 방식으로 중간 인덱스를 계산한다.

예시

1
2
3
4
5

int left = 2147483640;  // 큰 값
int right = 2147483647; // 매우 큰 값


int mid = (left + right) / 2;  // 이 경우 오버플로우를 일으킴

1
2
3
4

int left = 2147483640;
int right = 2147483647;

int mid = left + (right - left) / 2; // 이렇게 하면 오버플로우 방지 가능

-> left와 right의 차이가 항상 정수 범위 내에 있기 때문에 안전하다.

풀이

  1. 배열의 중간 요소를 루트로 선택합니다 (nums[mid]).
  2. 왼쪽 서브트리는 중간 요소 왼쪽의 부분 배열로부터 생성합니다.
  3. 오른쪽 서브트리는 중간 요소 오른쪽의 부분 배열로부터 생성합니다.