[leetcode]116.Populating Next Right Pointer Each Node

Populating Next Right Pointer 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.

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

제한사항

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

풀이1

function solution(root) {
    if (!root) return null;
    const queue = [root];
  
    while (queue.length) {
      const size = queue.length;
      const level = queue.slice();
      
      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
  }

풀이는 BFS 와 같이 level 1을 모두 연결하고, level2를 모두 연결 하는 방식으로 진행을 한다. 그래서 level별로 인식을 하기 위해, queue의 length를 size 변수에 받아, size만큼 node들을 연결하는 단계를 진행한다.

추가사항

binary tree에서 BFS와 같은 방식을 진행할 때, queue에 넣어서 진행을 하되, 어떻게 level별로 구별할 수 있을 까를 굉장히 많이 고민했는데, level을 진행을 다 하고 나서, 다음 level에는 몇개의 node가 존재하는 지를 미리 선언해서, 그 수 만큼 행위를 반복하면 되는 것이었다!!

내 깃헙 링크