LeetCode: 109번 (Convert Sorted List to Binary Search Tree) [JAVA]

문제 링크

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

Convert Sorted List to Binary Search Tree - LeetCode

풀이

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

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

 앞서 해결한 108번(Convert Sorted Array to Binary Search Tree)에서 자료구조 형태만 변한 문제이다. List 형태 자체로도 문제 해결에 접근할 수 있지만, 아무래도 앞선 문제를 해결하며 사용했던 재귀 기반의 서브 트리 구현 함수를 그대로 사용하고자 주어진 List 자료구조를 변경하는 방식을 사용했다.
 앞서 구현했던 재귀 함수가 nums 배열에 인덱스를 활용하여 접근하기에, 배열과 유사하게 인덱스 기반으로 접근 가능한 ArrayList 형태로 기존 List를 바꾼다. 그렇게 만들어진 ArrayList를, 앞서 구현했던 재귀 함수의 배열 인자 대신 넘겨, 이를 기반으로 인덱스 접근을 통해 트리를 구현해 나가면 된다.

 

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        ArrayList<Integer> nums = listToArrayList(head);
        return buildSubTree(nums, 0, nums.size() - 1);
    }

    ArrayList<Integer> listToArrayList(ListNode head) {
        ListNode node = head;

        ArrayList<Integer> convertResult = new ArrayList<>();

        while (node != null) {
            convertResult.add(node.val);
            node = node.next;
        }

        return convertResult;
    }

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

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

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

        return node;//노드 반환
    }
}

결과