Sorted Array to Binary Search Tree - 정렬된 배열을 이진 탐색 트리로 변환

정렬된 배열을 이진 탐색 트리로 변환하는 알고리즘이 있다.

아래와 같이 구성되어 있는데, Recursive 하게 작성되어 있다.

Code는 Java 언어로 작성 되어있다.

BinaryTree* sortedArrayToBST(int arr[], int start, int end) {

  if (start > end) return NULL;

  // same as (start+end)/2, avoids overflow.

  int mid = start + (end - start) / 2;

  BinaryTree *node = new BinaryTree(arr[mid]);

  node->left = sortedArrayToBST(arr, start, mid-1);

  node->right = sortedArrayToBST(arr, mid+1, end);

  return node;

}

 

BinaryTree* sortedArrayToBST(int arr[], int n) {

  return sortedArrayToBST(arr, 0, n-1);

}

출처: http://leetcode.com/2010/11/convert-sorted-array-into-balanced.html