LeetCode 654 - Maximum Binary Tree ( JavaScript )

 

 

안녕하세요besforyou입니다

 

이번 글은 LeetCode 654 - Maximum Binary Tree 문제 풀이입니다

 

---

문제 풀이

 

재귀 함수를 이용하여 Tree 자료구조를 생성하였습니다.

 

배열 안의 가장 큰 원소 값을 val 값으로 가지고, left 자식 node는 가장 큰 원소값 왼쪽의 subArray속의 가장 큰 원소값을 val로 가지고, right 자식 node는 가장 큰 원소값 오른쪽의 subArray속의 가장 큰 원소값을 val로 가지는 트리를 생성해야 합니다.

 

자바스크립트 함수는 내부의 함수를 가질 수 있으므로 매개변수 nums에 접근 가능한 내부 함수를 생성하여 재귀적으로 문제를 해결할 수 있습니다.

 

---

코. 드

 

var constructMaximumBinaryTree = function(nums) {
    return next(0, nums.length -1);
    function next(l, r) {
        if (l > r) return null;
        let nextIndex = -1, max = -Infinity;
        for (let i = l ; i <= r ; i++ ) {
            if (max < nums[i]) {
                nextIndex = i;
                max = nums[i];
            }
        }
        return {
            val : max,
            left : next(l, nextIndex - 1),
            right : next(nextIndex + 1 , r)
        }
    }
};

결과