LeetCode: 108번 (Convert Sorted Array to Binary Search Tree) [JAVA]

문제 링크

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

Convert Sorted Array to Binary Search Tree - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 재귀 기반 서브 트리 구현 함수 구현 (인자는 주어진 nums 배열, int start, int end)
   1) start > end라면 null을 리턴
   2) nums 배열 속 (start + end)/2 위치의 인덱스의 값을 가져와, 해당 값을 가진 노드를 생성
   3) 노드의 왼쪽 자식 노드에 재귀 함수를 호출한 결과를 저장. 이 때 start에는 start를, end에는 (start + end)/2 - 1을 지정
   4) 노드의 오른쪽 자식 노드에 재귀 함수를 호출한 결과를 저장. 이 때 start에는 (start + end)/2 + 1을, end에는 end를 지정
   5) 해당 노드 반환
2. 앞선 재귀 함수를 호출하여 그 결과값을 반환

 주어진 nums 배열을 바탕으로, height-balanced한 트리를 구성하라는 문제이다. 여기서 height-balanced란 높이간 균형을 뜻하는 것으로, 트리의 모든 노드 속 하위 두 서브 트리의 레벨 차이가 1이하임을 뜻한다.
 조건 자체가 레벨 차이만을 맞추면 되기 때문에, 트리를 어떻게 구성할 지에 대해선 제약이 없다. 여기서는 구현자의 재량이다 보니, 필자는 여기서 배열을 반으로 나누어 가며 트리를 구성하기로 했다. 주어진 nums 배열의 특정 구간을, 시작, 중간값, 끝으로 구성하여, 현재 노드를 중간값으로 만들고, 왼쪽 하위 서브트리를 시작 ~ 중간값-1로, 오른쪽 하위 서브트리를 중간값+1 ~ 끝으로 구현해나가는 방법이다.
 이처럼 만들기 위해선 재귀 기반으로 함수를 구현하는게 최적의 방식이다. 해당 재귀함수의 경우 우선 인자는 주어진 nums 배열과 특정 구간의 start 그리고 end를 받는다. 만약 주어진 start가 end 보다 크다면 null을 반환하면 된다. 그렇지 않다면 nums 배열에서 중간값인 (start + end)/2 위치의 값을 가져온 다음, 해당 값을 가지는 노드를 생성한다. 그 다음 노드의 왼쪽 하위 노드와 오른쪽 하위 노드에, 각각 재귀 함수를 호출한 결과를 저장해준다. 이 때 왼쪽의 경우 구간이 start부터 중간값-1, 오른쪽의 경우 구간이 중간값+1부터 end로 지정해주면 된다. 이후엔 현재 노드를 그대로 반환해준다.
 앞선 트리 구성 함수를 완료했다면, 주어진 nums 배열에 대하여 0~nums.length-1 구간에 대해 트리를 구성하도록 함수를 호출하고 그 결과를 반환하면 된다.

 

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildSubTree(nums, 0, nums.length - 1);
    }

    TreeNode buildSubTree(int[] nums, int start, int end) {//해당하는 구간에 대한 서브트리 생성 함수
        if (start > end) {
            return null;
        }

        int now = (start + end) / 2;//남은 구간의 가운데를 현재 서브 트리의 부모 노드로 지정
        TreeNode node = new TreeNode(nums[now]);//부모 노드 생성

        node.left = buildSubTree(nums, start, now - 1);//부모 노드를 제외한 왼쪽 구간에 대한 하위 서브 트리 생성
        node.right = buildSubTree(nums, now + 1, end);//부모 노드를 제외한 오른쪽 구간에 대한 하위 서브 트리 생성

        return node;//노드 반환
    }
}

결과