[LeetCode] 117. Populating Next Right Pointers in Each Node II, Medium

1. 문제

• 이진 트리가 주어질 때, 각 노드의 next가 동일 레벨의 오른쪽 노드를 가리키도록 구성하라.

2. 해결

/**
 * 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 > 0) {
        const queueSize = queue.length;
        
        for(let i =0; i< queueSize; i++) {
            const node = queue.shift();
            
            if(i < queueSize -1) {
                node.next = queue[0];
            }
            
            if(node.left) queue.push(node.left);
            if(node.right) queue.push(node.right);
        }
    }
    
    return root;
};

• 116번과 동일한 문제지만, 완전 이진 트리가 아니라는 특징이 있다.
• 116번에서 사용했던 재귀의 경우 이 문제를 풀 수 없다. 큐를 이용한 level 순회를 활용하여 풀어야 한다.