해당 포스팅은 릿코드 116번 Populating Next Right Pointers in Each Node 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였으며 BFS로 풀이하였다.

---

문제

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

모든 형제노드가 같은 level에 있고, 모든 부모노드에는 두 개의 자식 노드가 있는 완벽한 이진 트리가 제공된다.

각 노드가 다음 오른 쪽 노드를 가리키도록 next pointer를 설정하자. 다음 오른쪽 노드가 없으면 다음 포인터를 NULL로 설정해야 한다.

처음에는 모든 next pointer가 NULL로 설정된다.

---

예제

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]

Explanation: Given the above perfect binary tree (Figure A),
your function should populate each next pointer to point to its next right node, just like in Figure B.
The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

---

풀이

현재 level 노드(형제 노드)를 전부 방문하고 그 다음 level 노드(자식 노드)를 방문해야 하므로 BFS로 풀이했다.

---

로직 - BFS 이용

• 노드가 하나도 없는 트리일 시 즉시 null 리턴

if(!root) return null;

• 방문할 노드를 저장할 queue를 생성 후, root 노드를 넣어줌

const queue = [root];

• queue가 전부 빌 때까지 반복문 실행
• size = 모든 형제 노드를 방문하기 위해 queue 사이즈 저장
• level = 현재 queue에는 형제 노드만 저장되어 있으므로 queue를 복사해 저장. 각 형제 노드가 오른쪽 형제 노드를 pointer할 수 있게 된다.

while(queue.length) {
  const size  = queue.length;
  const level = [...queue];
  
  // 생략
  ...
  
}

• 형제노드 size만큼 loop돌리면서 pointer 설정.
• currentNode = queue에서 가장 앞에 있는 노드
• currentNode.next = level[i+1] ?? null = currentNode를 형제 노드를 저장해두었던 level을 이용해 그 다음 형제 노드를 가리키게끔 포인터 설정. 가장 마지막 형제 노드는 null를 pointer
• 각 형제 노드의 left, right 노드들을 queue에 추가

while(queue.length) {
  
  // 생략
  ...
  
  for(let i = 0; i < size; i++) {
    const currentNode = queue.shift();
    currentNode.next  = level[i + 1] ?? null;
    if(currentNode.left)  queue.push(currentNode.left);
    if(currentNode.right) queue.push(currentNode.right);
  }
}

---

전체 코드

/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function(root) {
    if(!root) return null;
    const queue = [root];
    
    while(queue.length) {
        const size  = queue.length;
        const level = [...queue];
        
        for(let i = 0; i < size; i++) {
            const currentNode = queue.shift();
            currentNode.next  = level[i + 1] ?? null;
            if(currentNode.left)  queue.push(currentNode.left);
            if(currentNode.right) queue.push(currentNode.right);
        }
    }
    return root;
};