정렬된 배열로 균형 잡힌 이진 탐색 트리를 만드려면
root의 값이 배열의 중앙값이여야한다.
예를 들어 정렬된 배열의 크기가 10이면, 중앙 인덱스값은 5이다.
중앙값을 선정했으므로, 인덱스 1~4 노드는 왼쪽 자식에 들어갈것이고, 6~10는 오른쪽 자식에 들어갈것이다. 왼쪽 자식에 들어가는 노드의 개수는 4개, 오른쪽에 들어가는 노드의 개수는 5개이므로 높이차는 1을 넘지 않는다. 재귀적으로 처리하면 모든 노드에 대해서 높이차가 1이 넘지 않을것이다.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode toBST(TreeNode root, int[] nums, int start, int end){
if(start>end)
return null;
int mid = (start+end)/2;
root = new TreeNode(nums[mid]);
root.left = toBST(root.left,nums,start,mid-1);
root.right = toBST(root.right,nums,mid+1,end);
return root;
}
public TreeNode sortedArrayToBST(int[] nums) {
return toBST(null,nums,0,nums.length-1);
}
}