[LeetCode] 662. Maximum Width of Binary Tree

😎풀이

1. 큐를 통해 각 레벨 별 너비를 계산해 최대 너비를 갱신함
2. 각 leaf 노드는 root 노드의 인덱스를 기준으로 각각 2 * idx, 2 * idx + 1임을 통해 거리를 계산
3. 이 때, 인덱스는 정수형의 범위보다 커질 수 있으므로 BigInt 활용
4. 최종적인 거리는 정수형의 범위를 보장한다는 규칙이 있으므로 정수형 변환 후 반환

type QueueType = [TreeNode, bigint][]

function widthOfBinaryTree(root: TreeNode | null): number {
    if(!root) return 0
    let queue: QueueType = [[root, 1n]]
    let maxWidth = 1n
    while(queue.length) {
        const firstIdx = queue[0][1]
        const lastIdx = queue.at(-1)[1]
        const width = lastIdx - firstIdx + 1n
        if(width > maxWidth) maxWidth = width
        const nextQueue: QueueType = []
        for(let i = 0; i < queue.length; i++) {
            const [node, idx] = queue[i]
            if(node.left) nextQueue.push([node.left, idx * 2n])
            if(node.right) nextQueue.push([node.right, idx * 2n + 1n])
        }
        queue = nextQueue
    }
    return Number(maxWidth)
};