Leetcode 108. Convert Sorted Array to Binary Search Tree

juniping·2025년 4월 10일

algorithm

오름차순의 Integer Array가 주어진다. 이를 height-balanced binary search tree 로 변환하라.

제한조건은 다음과 같다.

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is sorted in a strictly increasing order.

문제 이해 하기

Height-Balanced binary tree

어떤 노드에 대해서도 왼쪽과 오른쪽 서브트리의 높이 차이가 1을 넘지 않는 트리

해결 방법 고민

정렬된 배열을 이진 탐색트리로 만들면 된다.
중앙값을 루트로 설정하고 왼쪽과 오른쪽 트리를 구현하면 될 것 같다.
예를들어 {-1, 0, 1} 이 있을 때 0을 중앙값으로 잡고 왼쪽과 오른쪽은 각각 중앙값을 잡아서 트리를 만드는 걸 재귀로 반복하면 된다.

코드 작성


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return finder(nums, 0, nums.length-1);        
    }

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

        int mid = (left + right)/2;
        TreeNode node = new TreeNode(nums[mid]);

        node.left = finder(nums, left, mid-1);
        node.right = finder(nums, mid+1, right);

        return node;

    }
}