[LeetCode] 108. Convert Sorted Array to Binary Search Tree

😎풀이

재귀적으로 함수를 호출하며 풀이가 가능하다. 문제에서 언급되었듯이 오름차 순으로 정렬된 배열이기 때문에 배열 중앙 요소를 루트 노드로 설정하여 재귀적으로 호출하면 된다.

function sortedArrayToBST(nums: number[]): TreeNode | null {
    // 배열이 비어있으면 null 반환
    if (nums.length === 0) return null;
    
    // 재귀 헬퍼 함수 정의
    // start: 현재 부분 배열의 시작 인덱스
    // end: 현재 부분 배열의 끝 인덱스
    const helper = (start: number, end: number): TreeNode | null => {
        // 베이스 케이스: 시작이 끝보다 크면 null 반환
        if (start > end) return null;
        
        // 중간 인덱스 계산
        const mid = Math.floor((start + end) / 2);
        
        // 중간 값으로 새로운 노드 생성
        const root = new TreeNode(nums[mid]);
        
        // 왼쪽 서브트리 생성 (중간값 이전의 요소들)
        root.left = helper(start, mid - 1);
        
        // 오른쪽 서브트리 생성 (중간값 이후의 요소들)
        root.right = helper(mid + 1, end);
        
        return root;
    }
    
    // 전체 배열에 대해 헬퍼 함수 호출
    return helper(0, nums.length - 1);
}