[LeetCode] 1161. Maximum Level Sum of a Binary Tree

문제 출처: https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/

Maximum Level Sum of a Binary Tree - LeetCode

 

문제

이진 트리의 root가 주어지면, 루트의 레벨은 1이고, 루트의 자식은 레벨 2가 된다.

 

동일 레벨 노드들의 합을 구하고 그 합 중에서 값이 최대인 레벨의 가장 작은 값을 반환하라.

 

예제

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.

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

풀이

트리의 모든 레벨에 있는 노드를 한 번씩은 방문해야 하므로, 시간복잡도는 O(n)이 될 것이다. 문제 풀이의 핵심은 각 노드를 방문하면서 동일 레벨에 위치한 노드들의 합을 기록해 놓는 것이다.

 

트리의 모든 노드를 방문하기 위한 방법으로는 DFS 또는 BFS 방식이 존재하고, 여기서는 BFS를 선택하여 문제를 접근했다.

 

BFS를 선택한 이유는 동일 레벨 노드들의 합을 한 순간에 계산하기 위함이다.

BFS가 트리를 탐색하는 순서를 살펴보면 위의 그림과 같은데, 동일 레벨의 노드를 순차적으로 탐색하고 있는 것을 알 수 있다. 이를 이용하여 레벨의 합을 계산하고, 이 중 최대 값을 갖는 레벨을 구하도록 알고리즘을 구현할 수 있다.

 

다음은 BFS를 이용하여 문제를 해결한 코드이다.

var maxLevelSum = function (root) {
    let ans = 0;

    let q = [root];
    let level = 1;
    let maxSum = -Infinity;
    while (q.length) {
        const nextQ = [];
        let currLevelSum = 0;
        for (let i = 0; i < q.length; i++) {
            const node = q[i];

            curLevelSum += node.val;

            if (q.left != null) { nextQ.push(q.left); }
            if (q.right != null) { nextQ.push(q.right); }
        }

        if (maxSum < curLevelSum) {
            ans = level;
            maxSum = curLevelSum;
        }

        level += 1;
        q = nextQ;
    }

    return ans;
}

 

 

Github: 1161.js

opwe37/Algorithm-Study