Leetcode 108. 정렬된 배열의 이진 탐색 트리 변환

정렬된 배열을 받아 높이 균형 이진 탐색 트리로 변환하라.
높이 균형이란 모든 노드의 두 서브 트리 간 깊이 차이가 1 이하인 것을 말한다.

내가 푼 코드와 책(자바 알고리즘 인터뷰 - 박상길 저)에 나온 코드를 비교한다.
우선, 두 코드 모두 leetcode 제출 후 Runtime 0ms가 나왔다. 하지만 시간 복잡도는 다르다.

1️⃣ 내 코드 & 2️⃣ 책 코드

class Solution { // 1️⃣ 내 코드
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) return null;
        TreeNode node = new TreeNode(nums[midIdx(nums.length)]);
        int[] leftNums = new int[midIdx(nums.length)];
        for (int i=0; i < midIdx(nums.length); i++) {
            leftNums[i] = nums[i];
        }

        int[] rightNums = new int[nums.length - midIdx(nums.length)-1];
        for (int i=midIdx(nums.length)+1; i<nums.length; i++) {
            rightNums[i-midIdx(nums.length)-1] = nums[i];
        }
        
        node.left = sortedArrayToBST(leftNums);
        node.right = sortedArrayToBST(rightNums);
        return node;
    }

    public int midIdx(int len) {
        int midIdx;
        return midIdx = len / 2;
    }
}

class Solution { // 2️⃣ 책 코드
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) return null;
        return construct(nums, 0, nums.length - 1);
    }
    public TreeNode construct(int[] nums, int lo, int hi) {
        if (lo > hi) return null;
        // 인덱스의 중앙값 계산, 소숫점은 내림
        int mid = lo + (hi - lo)/2; // 🟠
        // 배열의 중앙값으로 노드 생성
        TreeNode node = new TreeNode(nums[mid]);
        node.left = construct(nums, lo, mid - 1);
        node.right = construct(nums, mid+1, hi);
        return node;
    }
}

1️⃣과 2️⃣의 로직 차이점

1️⃣은 매 호출마다 왼쪽/오른쪽 서브 배열을 새로 생성하고,
2️⃣는 동일 배열에 대해 인덱스 범위만 이동한다.

🔸 1️⃣은 sortedArrayToBST() 메서드 자체를 재귀 구조로 설계하였고 2️⃣는 construct() 메서드를 만들어서 재귀시켰다.

🔸 1️⃣은 nums를 중앙값 기준으로 좌, 우로 갈랐다. for 문을 통해 leftNums와 rightNums를 만든다. 그렇게 나눠 놓은 nums를 재귀할 함수의 인자로 넣었다.
2️⃣는 주어진 nums를 조작하지 않고, nums의 index 역할을 int lo, int hi라는 포인터가 담당한다. 이 포인터들이 옮겨 가며 중앙값을 구한다. 그러므로 문제에서 주어진 nums와 lo, hi가 재귀할 함수의 인자로 들어간다.

1️⃣, 2️⃣ 분석 & 시간·공간 복잡도

코드 1️⃣ 분석: 복사 비용이 큼

: 서브 배열 복사 방식

매 호출마다 서브 배열을 2개씩 새로 생성하면 총 복사량을 처리하는 시간이 O(nlogn)으로 불필요하게 커진다. 공간 복잡도도 마찬가지로 추가 공간 O(nlogn)이 쓰인다.

🔸 O(nlogn)인 이유
n : 입력 배열(nums)의 길이, logn : 배열이 절반씩 줄어드는 깊이

현재 배열 길이 = m일 때,
왼쪽 오른쪽 서브 배열을 만든뒤 for문으로 복사하는 작업의 시간 복잡도는 O(m)

각 재귀 레벨마다 서브 배열 복사 총합이 O(n) 발생하고 레벨 수가 O(log n)이므로 합계 O(nlogn)

코드 2️⃣ 분석

: 인덱스 재귀 방식

반면에 코드 2️⃣에서는 시간 O(n), 추가 공간 O(log n)

🔸 시간 복잡도 O(n)인 이유
원소 하나 당 O(1)이 걸린다. (중간 인덱스 계산, 노드 하나 생성, 왼쪽/오른쪽 부분으로 재귀 : 배열 복사 없음)

🔸 추가 공간 O(log n)인 이유
출력 공간(최종 생성되는 BST 노드들 O(n)) 외 알고리즘이 추가로 쓰는 메모리가 O(log n)이다.
한번의 호출 프레임이 갖는 공간 O(1), 재귀 최대 깊이 O(log n)
따라서 추가 공간은 O(log n)

🟠 중앙 index 계산의 안정성

왜 int mid는 (lo + hi) / 2가 아니고 lo + (hi - lo) / 2인가?

(lo + hi) / 2는 두 인덱스의 합이 int 범위를 넘으면 오버플로가 난다.
lo + (hi - lo) / 2는 차이를 먼저 구해서 범위를 좁히므로 비교적 안전하다.

LeetCode 108의 입력 크기 제약은 다음과 같다.

Constraints:

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4

int의 최댓값은 2,147,483,647 ( 2 * 10^9 정도 )이다.
배열 길이 n이 10^9급이면 위험할 수 있으나 문제의 범위에서 (lo + hi)가 2 * 10^9이 나올 리는 없으니 실제로 오버플로가 발생할 가능성은 없다.
일반적인 코딩 테스트에서는 보통 안전하지만 라이브러리/서비스 코드에서는 입력 상한을 장담 못하니 lo + (hi - lo) / 2와 같은 안전 패턴이 권장된다.