LeetCode 108번 - Convert Sorted Array to Binary Search Tree

문제 살펴보기

주어진 int 자료형 배열을 이용해 이진 탐색 트리(Binary Search Tree)를 만드는 문제이다.

 

* 이진 탐색 트리 : 왼쪽 자식 노드는 부모 노드보다 작은 값을, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가진 트리 구조를 의미한다.

 

---

생각해보기

 

만약 주어진 배열이 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이라면?

위와 같은 모습의 이진 트리가 만들어져야 한다. (*점선은 빈 노드를 의미합니다)

 

그러기 위해서는 우선, 배열에서 부모 노드에 저장할 값을 꺼낸다.

그러고 나서 해당 값을 기준으로 2개의 묶음으로 나눈다.

 [0, 1, 2, 3, 4] 5 [6, 7, 8, 9, 10]

 

트리의 다음 단계로 넘어간다.

각 묶음에서 다시 부모 노드에 저장할 값을 꺼내고, 또 2개의 묶음으로 나눈다.

[0, 1] 2 [3, 4]  / [6, 7] 8 [9, 10]

 

위 작업을 다시 반복한다.

 

이제 각 묶음에는 숫자가 2개밖에 남아있지 않기 때문에, 어떤 숫자를 부모 노드에 저장할 값으로 꺼낼지 결정해야 한다.

 

두 숫자 중 큰 수를 꺼낸다면, 남아있는 숫자는 현재 노드를 기준으로 왼쪽 자식 노드에 들어가게 된다.

[0] 1 / [3] 4 / [6] 7 / [9] 10

남아있는 값들은 왼쪽 자식 노드에 넣고, 오른쪽 자식 노드에는 null값을 넣어줘야 한다.

 

그래서 최종적으로는 다음과 같은 구조가 만들어진다.

[5,2,8,1,4,7,10,0,null,3,null,6,null,9]

 

+ 만약 두 숫자 중 작은 수를 꺼낸다면 남아있는 수는 오른쪽 자식 노드에 들어가게 된다.

0 [1] / 3 [4] / 6 [7] / 9 [10]

 

---

풀어보기

재귀함수를 이용했다.

 

배열과, 배열의 시작 인덱스(0), 마지막 인덱스(nums.length-1)을 sortedArrayToBST 메서드의 파라미터로 넣는다.

 

위에서 받아온 시작 인덱스(start)와 마지막 인덱스(end)를 이용해 부모 노드에 저장할 값에 해당하는 인덱스를 계산하고,

변수 mid에 대입한다.

 

mid에 해당하는 값을 가진 TreeNode root를 생성한다.

 

root의 왼쪽으로는 mid값을 기준으로 왼쪽에 있는 묶음을 보내야 한다.

따라서 int 배열, start, mid-1을 sortedArrayToBST 메서드의 파라미터로 넣는다.

 

root의 오른쪽으로는 mid값을 기준으로 오른족에 있는 묶음을 보내야 한다.

따라서 int 배열 nums, mid+1, end를 sortedArrayToBST 메서드의 파라미터로 넣는다.

 

만약 파라미터로 넣은 start가 mid-1보다 크거나,

또는 mid+1이 end보다 크다면 값이 없다는 뜻이므로 null을 반환해야 한다.

 

따라서 메서드의 첫 부분에 조건문을 추가했다.

public TreeNode sortedArrayToBST(int[] nums) {
    return sortedArrayToBST(nums, 0, nums.length-1);
}
public TreeNode sortedArrayToBST(int[] nums, int start, int end){
    if(start > end){
        return null;
    }
    int mid = (int)Math.ceil(((float)start + end)/2);
    TreeNode root = new TreeNode(nums[mid]);
    root.left = sortedArrayToBST(nums, start, mid-1);
    root.right = sortedArrayToBST(nums, mid+1, end);
    return root;
}

 

 

반대 모양으로 만드는 경우

public TreeNode sortedArrayToBST(int[] nums) {
    return sortedArrayToBST(nums, 0, nums.length-1);
}
public TreeNode sortedArrayToBST(int[] nums, int start, int end){
    if(start > end){
        return null;
    }
    int mid = (start + end)/2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = sortedArrayToBST(nums, start, mid-1);
    root.right = sortedArrayToBST(nums, mid+1, end);
    return root;
}