LeetCode 108. Convert Sorted Array to Binary Search Tree 자바 문제 풀이

문제

Convert Sorted Array to Binary Search Tree - LeetCode

문제 해결 방법

-정렬된 어레이를 가지고 바이너리 서치트리에 밸런스 있게 넣는 문제입니다.

-이진트리는 밸런스가 맞아야 하므로, 바이너리 서치 트리를 만드는 법을 아느냐고 묻는 문제입니다.

1. 바이너리 서치 트리는 보통 재귀함수를 사용해서 구현합니다.
2. root는 전체 어레이의 중간값을 넣습니다.
3. 왼쪽노드역시 왼쪽부분의 중간값을 넣습니다.
4. 오른쪽 노드 역시 오른쪽 부분의 중간값을 넣습니다.

-재귀함수가 아닌 반복문으로 구현할경우, 코드자체가 복잡해지고 이해하기 어렵지만, 오버플로우의 위험성이 사라진다는 장점이 있습니다.

시간복잡도: O(log n), 공간복잡도: O(n)

https://github.com/eunhanlee/LeetCode108.ConvertSortedArraytoBinarySearchTree.git

public class Solution {

    /**
     * 주어진 정렬된 배열을 이용하여 이진 탐색 트리를 생성합니다.
     *
     * @param nums 정렬된 배열
     * @return 생성된 이진 탐색 트리의 루트 노드
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        // 주어진 배열이 비어있지 않음을 가정하므로 null 체크는 생략됨
        // if (nums == null || nums.length == 0) return null;

        return constructBST(nums, 0, nums.length - 1);
    }

    /**
     * 주어진 범위 내에서 이진 탐색 트리를 재귀적으로 생성합니다.
     *
     * @param nums   정렬된 배열
     * @param start  현재 범위의 시작 인덱스
     * @param end    현재 범위의 끝 인덱스
     * @return 생성된 서브 트리의 루트 노드
     */
    private TreeNode constructBST(int[] nums, int start, int end) {
        // start가 end보다 큰 경우, 더 이상 분할할 수 없으므로 null 반환
        if (start > end) return null;

        // 현재 범위의 중간 인덱스를 계산하여 중간 값을 루트로 설정
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(nums[mid]);

        // 중간 값을 기준으로 왼쪽과 오른쪽 서브트리 재귀적으로 생성
        root.left = constructBST(nums, start, mid - 1);
        root.right = constructBST(nums, mid + 1, end);

        return root;
    }
}

public class Solution2 {
    /**
     * 주어진 정렬된 배열을 이용하여 이진 탐색 트리를 생성합니다.
     *
     * @param nums 정렬된 배열
     * @return 생성된 이진 탐색 트리의 루트 노드
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        // 주어진 배열이 비어있지 않음을 가정하므로 null 체크는 생략됨
        // if (nums == null || nums.length == 0) return null;

        int start = 0;
        int end = nums.length - 1;

        TreeNode root = new TreeNode(0); // 임시 루트 노드 생성

        Deque<TreeNode> nodeStack = new ArrayDeque<>(); // 노드 스택
        Deque<Integer> startIdxStack = new ArrayDeque<>(); // 시작 인덱스 스택
        Deque<Integer> endIdxStack = new ArrayDeque<>(); // 끝 인덱스 스택

        TreeNode current = root;
        int currStart = start;
        int currEnd = end;
        int mid;

        while (true) {
            mid = (currStart + currEnd) / 2;
            current.val = nums[mid]; // 현재 노드 값 설정

            if (mid < currEnd) {
                current.right = new TreeNode(0); // 오른쪽 노드 생성
                nodeStack.push(current.right);
                startIdxStack.push(mid + 1);
                endIdxStack.push(currEnd);
            }

            if (currStart < mid) {
                current.left = new TreeNode(0); // 왼쪽 노드 생성
                current = current.left;
                currEnd = mid - 1;
            } else {
                if (nodeStack.isEmpty()) {
                    break;
                }
                current = nodeStack.pop();
                currStart = startIdxStack.pop();
                currEnd = endIdxStack.pop();
            }
        }

        return root;
    }
}