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

문제

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.

다음 오른쪽 노드를 가리키도록 각 포인터를 채웁니다. 다음 오른쪽 노드가 없으면 다음 포인터를 'NULL'로 설정해야 합니다.

처음에 모든 다음 포인터는 'NULL'로 설정됩니다.

예시

Example 1:

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.

Example 2:

Input: root = []
Output: []

제약

• The number of nodes in the tree is in the range [0, 212 - 1].
• -1000 <= Node.val <= 1000

코드

const connect = (root) => {
    if (!root) return root;
    
    const queue = [[0, root]];
    
    while (queue.length) {
        const [curNodelev, currNode] = queue.shift();
        
        if (queue.length) {
            const [nextNodelev, nextNode] = queue.shift();
            currNode.next = curNodelev === nextNodelev ? nextNode : null;
            queue.unshift([nextNodelev, nextNode]);
        } else {
            currNode.next = null;
        }
        
        currNode.left && queue.push([curNodelev + 1, currNode.left]);
        currNode.right && queue.push([curNodelev + 1, currNode.right]);
    }
    
    return root;
};

풀이

• bfs 순회를 진행하기 위해 노드를 담을 queue 를 준비한다. (첫번째 노드를 미리 세팅한다. [[0, root]])

• queue 의 원소 형태는 [해당노드의 레벨, 해당노드의 값] 형태로 저장해 놓는다.

• queue 가 비워질 때까지 bfs를 진행한다.

• 매 순회마다 아래와 같은 로직으로 현재노드의 다음노드를 지정한다.

  • 만약 queue 에 현재 노드를 shift 해왔는데 이외에 다른 노드가 있다면 (if (queue.length)) 이 노드를 다음 노드를 칭하여 함께 shift 해온다.
  • 현재노드의 레벨과 다음 노드의 레벨이 같다면 현재 노드의 next 를 다음 노드로 설정하고 레벨이 다르다면 현재 노드의 next 를 null 로 설정한다. 그리고 다음 노드를 다시 queue에 unshift 하여 맨 앞에 복원시킨다.
  • 만약 queue 에 현재노드만 존재한다면 다음 노드가 없는것으로 간주하여 현재 노드의 next 를 null로 설정한다.