[leetcode] Convert Sorted Array to Binary Search Tree

유의할점

풀이

정렬된 배열로 균형 잡힌 이진 탐색 트리를 만드려면

root의 값이 배열의 중앙값이여야한다.

예를 들어 정렬된 배열의 크기가 10이면, 중앙 인덱스값은 5이다.

중앙값을 선정했으므로, 인덱스 1~4 노드는 왼쪽 자식에 들어갈것이고, 6~10는 오른쪽 자식에 들어갈것이다. 왼쪽 자식에 들어가는 노드의 개수는 4개, 오른쪽에 들어가는 노드의 개수는 5개이므로 높이차는 1을 넘지 않는다. 재귀적으로 처리하면 모든 노드에 대해서 높이차가 1이 넘지 않을것이다.

코드

Java

/**
 * 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);
    }
}