[LeetCode 108] Convert Sorted Array to BST (Java)

🚀 문제 분석

• 목표: 오름차순으로 정렬된 정수 배열을 높이 균형 이진 탐색 트리(Height-Balanced BST)로 변환합니다.
• 핵심 제약: 모든 노드에서 두 서브트리의 깊이 차이가 1 이하여야 합니다.
• 해결 실마리: 배열이 이미 정렬되어 있으므로, 중간값(Median)을 루트로 선택하면 좌우 서브트리에 배분되는 노드 수가 균등해져 자연스럽게 균형이 잡힙니다.

💡 해결 전략: 분할 정복 (Divide and Conquer)

배열의 범위를 절반씩 쪼개며 트리를 구성하는 방식입니다.

1. 중앙 요소 선택: 현재 범위 [start, end]의 중앙값(mid)을 찾아 현재 서브트리의 루트 노드로 생성합니다.
2. 좌우 분할:
   • start부터 mid - 1까지의 범위는 왼쪽 자식 노드로 보냅니다.
   • mid + 1부터 end까지의 범위는 오른쪽 자식 노드로 보냅니다.
3. 재귀적 연결: 범위가 역전(start > end)될 때까지 이 과정을 반복하여 전체 트리를 완성합니다.

💻 구현 코드 (Java)

public class Solution_Leetcode_108 {

    public TreeNode sortedArrayToBST(int[] nums) {
        // 배열 전체 범위를 대상으로 트리 구성 시작
        return organize(nums, 0, nums.length - 1);
    }

    private TreeNode organize(int[] nums, int start, int end) {
        // 기저 사례: 더 이상 처리할 범위가 없으면 null 반환
        if (start > end) {
            return null;
        }

        // 중간값 계산: 비트 연산(Right Shift)을 통해 가독성과 미세한 성능 최적화
        // (start + end) / 2 와 동일한 로직
        int mid = (start + end) >> 1;

        // 중앙값을 루트로 하여 좌우 서브트리를 재귀적으로 빌드
        TreeNode left = organize(nums, start, mid - 1);
        TreeNode right = organize(nums, mid + 1, end);

        // 현재 노드 생성 및 계산된 자식 노드들 연결
        return new TreeNode(nums[mid], left, right);
    }
}

🧐 기술적 고찰 (수정본)

• 중간값 계산 방식: (start + end) / 2 대신 비트 우측 시프트 연산(>> 1)을 사용했습니다. 이는 나눗셈 연산에 비해 CPU 사이클 소모가 적은 저수준 연산으로 처리되며, 이진 탐색 기반 로직에서 중간 인덱스를 도출하는 의도를 명확히 합니다.
• 공간 복잡도: 별도의 배열 슬라이싱이나 복사 없이 원본 배열의 인덱스 범위(start, end)만 재귀 인자로 넘겨 처리했습니다. 따라서 추가 메모리 할당 없이 재귀 호출 스택 깊이인 $O(\log N)$ 내에서 동작합니다.
• 시간 복잡도: 모든 원소를 한 번씩 노드로 변환하므로 $O(N)$에 해결됩니다.