[LeetCode] 108. Convert Sorted Array to Binary Search Tree

문제 출처: https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

Convert Sorted Array to Binary Search Tree - LeetCode

 

문제

오름차순으로 정렬되어 있는 정수 배열 nums가 주어지면, 균형 이진탐색트리로 만들어라.

 

균형 이진트리는 모든 노드에서의 두 하위트리의 높이 차가 1 이하인 이진트리를 말한다.

 

예제

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]

Input: nums = [1,3]
Output: [3,1]

Explanation: [1,3] and [3,1] are both a height-balanced BSTs.

 

풀이

이진탐색트리(BST)의 특성을 물어보는 문제이다.

 

이진탐색트리는 트리를 구성하는 어떤 노드라도 좌측 하위트리는 자신의 값보다 작은 원소들로 구성되어 있어야 하고, 우측 하위트리는 자신의 값보다 큰 원소들로 구성되어 있다는 특징이 있다.

 

이러한 특징에 기반하여 높이가 균형 있도록 트리를 구성하기 위해서는 정렬된 배열에서 중앙에 위치한 값을 부모 노드로 만드는 전략을 취할 수 있다.

 

중앙의 값을 선택해 트리 노드로 만들고, 중앙을 기점으로 외쪽과 오른쪽 원소들에 대해서 반복적으로 중앙값을 선택해 노드로 만드는 과정을 통해서 균형 잡힌 트리를 만들 수 있다.

var sortedArrayToBST = function(nums) {
	function buildBST (nums, lo, hi) {
    	if (lo > hi) { return null; }
        
        const mid = lo + Math.floor((hi - lo) / 2);
        
        consto newNode = new TreeNode(nums[mid]);
        newNode.left = buildBST(nums, lo, mid-1);
        newNode.right = buildBST(nums, mid+1, hi);
        
        return newNode;
    }
    
    return buildBST(nums, lo, hi);
}

 

Github: 108.js

GitHub - opwe37/Algorithm-Study