[LeetCode] 116. Populating Next Right Pointers in Each Node

😎풀이

BFS를 활용해 풀이해야 하는 문제이다.

같은 depth의 node를 연결하면 되는 문제임

/**
 * Definition for _Node.
 * class _Node {
 *     val: number
 *     left: _Node | null
 *     right: _Node | null
 *     next: _Node | null
 *     constructor(val?: number, left?: _Node, right?: _Node, next?: _Node) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function connect(root: _Node | null): _Node | null {
    if (!root) return null;
    const queue = [[root]];
    while (queue.length) {
        const currents = queue.pop();
        const nexts = [];
        for (let i = 0; i < currents.length; i++) {
            const current = currents[i];
            // 다음 노드와 연결
            if (i < currents.length - 1) {
                current.next = currents[i + 1];
            }
            // 자식 노드들 추가
            if (current.left) nexts.push(current.left);
            if (current.right) nexts.push(current.right);
        }
        // 다음 레벨의 노드들이 있을 때만 queue에 추가
        if (nexts.length > 0) {
            queue.push(nexts);
        }
    }
    return root;
}