리트코드 - 108. Convert Sorted Array to Binary Search Tree

리트코드 - 108. Convert Sorted Array to Binary Search Tree

출처 - https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 정수 배열 nums가 오름차순으로 정렬되어 있을 때, 이 배열을 높이가 균형 잡힌 이진 검색 트리로 변환하세요.

 

의사코드

함수 sortedArrayToBST     if (nums == null || nums.length == 0)         null 리턴     sortedArrayToBST(nums, 0, nums.length - 1) 함수 sortedArrayToBST(int[] nums, int left, int right)     if (left > right)         null 리턴     mid = (left + right) / 2     TreeNode node = new TreeNode(nums[mid])     node.left = sortedArrayToBST(nums, left, mid - 1)     node.right = sortedArrayToBST(nums, mid + 1, right)     node 리턴

 

풀이코드

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0){
            return null;
        }

        return sortedArrayToBST(nums, 0, nums.length - 1);

    }

    public TreeNode sortedArrayToBST(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        int mid = (left + right) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = sortedArrayToBST(nums, left, mid - 1);
        node.right = sortedArrayToBST(nums, mid + 1, right);

        return node;
    }
}

 

코드설명

배열이 오름차순으로 정렬이 되어 있을 때, 균형잡힌(=양쪽의 레벨이 같은) 이진트리를 구현하는 문제이다.

이진트리를 만드는 방법은 다양한 것이 있지만 가장 기초적인 중간값을 root로 하여 왼쪽과 오른쪽을 나누는 방법을 택했다.

 

기존 주어진 함수를 오버로딩하여 처음값과 끝값을 추가적으로 받도록 하였다.

이 로직은 배열 이진 탐색과 완전히 동일하다.

 

먼저 전체 배열값을 받아 중간값(mid)를 찾고 이것을 node로 만든다. 처음 만들어진 노드는 root노드가 된다.

그리고 이 노드의 왼쪽을 다시 배열의 왼쪽(0부터 mid - 1 까지)을 재귀적으로 함수를 호출하여 중간값을 찾아 연결한다.

마찬가지로 오른쪽에는 배열의 오른쪽(mid + 1 부터 right까지)에 대해서 재귀적으로 중간값을 찾아 node를 연결한다.

 

중요한 부분은 if (left > right) 부분인데 이것은 절대로 left >= right가 되면 안된다.

이건 배열 크기가 짝수인 경우 예를 들기 쉽다. 예를 들어 크기 4짜리 배열이 있다고 하면,,

처음에 mid = 1로 찾아 이것이 root가 될 것이다.

다음으로 node의 left 부분을 재귀적으로 호출하기 위해 (배열, left, mid -1) 이 매개변수로 전달되는데

left = mid-1 = 0이다. 만약 left > right 조건이 아니라 left >= right 이면 null이 붙어버린다.

 

left > right 조건이 붙어야 0번째 배열값을 left 노드에 붙일 수 있다.

마찬가지로 오른쪽 노드 붙일때에도 동일한 로직을 거치고

최종적으로 이런 노드를 얻을 수 있다.

 

시간복잡도 - O(n) (이진 탐색과 비슷하지만, 전체를 다 탐색하므로 n이다.)

공간복잡도 - O(n)

 

문제를 풀며 생각한 흐름과 배운 점

처음에는 오름차순으로 접근한 점에 초점을 맞추고 순차적으로 노드를 만들다보니 root를 어떤 것으로 정할지가 애매했다.

따라서 root를 먼저 찾아야 했는데, 어떤 값을 root로 할지에 대해 너무 깊은 고민을 했다.

균형잡힌 이진트리는 경우의 수가 생각보다 꽤 있었기 때문이다.

 

일단 가운데 값을 기준으로 하여 root로 정하고 푸는 방법을 택했고, 올바른 방법이었다.

한가지만 빼고..

 

리팩토링

// int mid = (left + right) / 2;
int mid = left + (right - left) / 2;

이전 문제에서 오버플로우를 겪었기 때문에 mid값을 이런식으로 찾았어야 했는데 그냥 나누어버렸다.

단순히 두 개의 값을 더해서 나누는게 아니라 '1)시작값 2) 중간값 3)시작값과 중간값을 더함'의 과정을 거치는 것이다.

이렇게 해야 연산할때 타입의 값을 벗어나지 않게 된다.

 

다른 코드

다른 코드들을 찾아봤는데 내 코드와 완전히 똑같았다.

확실히 고민을 30분 이상하고 해결이 안되면 다른 코드를 보고 참고하는게 빠른 길인것 같다.

 

정리

배열이 주어졌을 때 균형잡힌 이진탐색 트리 만드는 법.