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

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

• https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/description/

풀이

• 트리 너비 우선 순회 문제
• root의 level이 1임에 주의 -> return할 때 +1 해주기

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */

import java.util.Deque

class Solution {
    fun maxLevelSum(root: TreeNode?): Int {
        // levelSum[i]: sum of nodes on i-th level of the tree
        val levelSum = mutableListOf<Long>()

        // Pair<current tree node, current tree node's level>
        val q = ArrayDeque<Pair<TreeNode?, Int>>()
        q.addLast(Pair(root, 0))
        while(!q.isEmpty()){
            val curNode = q.first().first
            val curLevel = q.first().second
            q.removeFirst()

            if(curNode == null) continue

            if(levelSum.size <= curLevel) levelSum.add(curNode.`val`.toLong())
            else levelSum[curLevel] = levelSum[curLevel] + curNode.`val`.toLong()

            if(curNode.left != null) q.addLast(Pair(curNode.left, curLevel+1))
            if(curNode.right != null) q.addLast(Pair(curNode.right, curLevel+1))
        }
        
        return levelSum.indexOf(levelSum.max()) + 1
    }
}