LeetCode 108 - Convert Sorted Array to Binary Search Tree (Easy)

 

💡 문제

LeetCode - 108번

 

🎯 풀이 과정

구간 nums 에 대해서 이진탐색트리를 구성하기 위해 nums 의 중간값을 루트노드로하고

해당 노드를 제외한 나머지 두 구간에 대해 재귀적으로 트리를 구성하면 됩니다.

 

이 방식으로 문제를 해결할 수 있는 이유는 뭘까요?

구간 nums의 개수를 x 라고 하고 간단한 증명을 해보겠습니다.

x 가 짝수(2n)이면 나머지 두 구간은 (n, n-1) 로 나뉘고, 홀수(2n-1)라면 (n-1, n-1) 로 나뉩니다.

때문에 두 트리간의 높이 차이가 1보다 큰 경우는 없게 됩니다.

 

👨‍💻 코드

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
     function generateBST(lowerbound, upperbound) {
        if (lowerbound > upperbound) {
           return undefined
        }

         if (lowerbound === upperbound) {
            return new TreeNode(nums[lowerbound], undefined, undefined)
         }

        const mid = Math.floor((lowerbound + upperbound + 1) / 2)

        const leftTreeRootNode = generateBST(lowerbound, mid-1)
        const rightTreeRootNode = generateBST(mid+1, upperbound)

        const root = new TreeNode(nums[mid], leftTreeRootNode, rightTreeRootNode)

        return root
     }

     const tree = generateBST(0, nums.length-1)

     return tree
};