Daily LeetCode Challenge - 662. Maximum Width of Binary Tree

Problem From.
https://leetcode.com/problems/maximum-width-of-binary-tree/

오늘 문제는 tree 가 주어질때 그 tree 의 depth 에 따른 기준에서 가장 길이가 긴 부분을 찾는 문제였다.

이 문제는 BFS 로 풀 수 있었는데, 각 노드마다 index 번호를 붙인다고 생각하고, 각 depth 를 탐색할때마다 모드 노드들을 돌면서 (제일 오른쪽의 인덱스 - 제일 왼쪽의 인덱스 + 1) 를 하면 길이가 나온다. BFS 를 풀때 각 depth 의 모든 노드를 보려면, queue 를 순회할때, queue 의 길이만큼 반복되도록 하면 된다.

/**
 * 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
 * }
 */
class Solution {
  fun widthOfBinaryTree(root: TreeNode?): Int {
    if (root == null) return 0

    var answer = 0L
    val q : Queue<Pair<TreeNode, Long>> = LinkedList()
    q.add(Pair(root, 0L))

    while (q.isNotEmpty()) {
      var min = Long.MAX_VALUE
      var max = Long.MIN_VALUE
      repeat(q.size) {
        val (node, id) = q.poll()

        min = minOf(min, id)
        max = maxOf(max, id)

        if (node.left != null)
          q.add(Pair(node.left!!, id * 2L))

        if(node.right != null)
          q.add(Pair(node.right!!, id * 2L + 1))
      }
      answer = maxOf(answer, (max - min + 1))
    }
    return answer.toInt()
  }
}