[leetCode/JS] 1161. Maximum Level Sum of a Binary Tree

난이도 [ 🤔 ] Medium

 

문제 설명 

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on. Return the smallest level x such that the sum of all the values of nodes at level x is maximal.

 

이진 트리의 루트(root)가 주어집니다. 루트의 레벨은 1이고, 그 자식들의 레벨은 2, 그다음은 3으로 이어집니다.각 레벨에 있는 모든 노드 값의 합을 구했을 때, 그 합이 최대가 되는 가장 작은 레벨 x를 반환하세요.

포인트 1: 합이 최대인 레벨을 찾아야 함.
포인트 2: 만약 합이 같은 레벨이 여러 개라면, 그중 숫자가 더 작은 레벨(더 위쪽에 있는 레벨)을 선택해야 함.

 

 

입출력 예

Example 1:

Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation: Level 1 sum = 1. Level 2 sum = 7 + 0 = 7. Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

 

 

Example 2:

Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2

 

 

 

Constraints

• The number of nodes in the tree is in the range [1, 10^4]. 
• -10^5 <= Node.val <= 10^5

 

 

 

---

내 솔루션

 

/**
 * 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 {TreeNode} root
 * @return {number}
 */
var maxLevelSum = function (root) {
    let maxSum = -Infinity;
    let maxLevel = 1;
    let level = 1;
    let que = [root];

    while (que.length > 0) {
        let currentSize = que.length;
        let currentSum = 0;
        for (let i = 0; i < currentSize; i++) {
            let node = que.shift();
            currentSum += node.val;

            if (node.left) que.push(node.left);
            if (node.right) que.push(node.right);
        }

        if (currentSum > maxSum) {
            maxSum = currentSum;
            maxLevel = level;
        }
        level++;
    }
    return maxLevel;
};

 

감상평

• 문제 보고 음.. BFS를 사용해야 겠네
• BFS로 레벨 별로 돌아야 하니까 while 속에 for문으로 돌리면서 합계를 구해야하는군!
• for문이 끝나면 누가 더큰지 비교해서 제일 큰 값의 레벨을 리턴하면 된다!
• 라는 생각으로 풀면 쉽게 풀림.

 

 

 

Beast 100% 달성 코드 첨부

• 로직와 알고리즘 모두 똑같은데, 찿이가 que 대신에 head하는 index를 이용해서 반복함.
• shift() 같은 경우 [1,2,3,4] 에서 1이 빠지면 나머지 3칸이 이동하는 시스템이라고함. 그래서 더 오래 걸림.
• 단순히 head 라는 index만 ++ 하니까 런타임이 줄어든다고 한다.
• BFS가 잘 도는데 느리다고 빠꾸 먹으면 head BFS를 떠올릴 것

/**
 * 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 {TreeNode} root
 * @return {number}
 */
var maxLevelSum = function(root) {
    if(!root) return -1;

    const queue = [root];
    let head = 0;

    let maxValue = -Infinity;
    let maxIndex = 1;
    let currentLevel = 1;

    while (head < queue.length) {
        const levelSize = queue.length - head;
        let levelSum = 0;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue[head++];
            levelSum += node.val;

            if(node.left) queue.push(node.left);
            if(node.right) queue.push(node.right);
        }

        if(levelSum > maxValue) {
            maxValue = levelSum;
            maxIndex = currentLevel;
        }

        currentLevel++
    }

    return maxIndex
};