Portfolio

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.

Constraints:

The number of nodes in the tree is in the range [0, 212 - 1].

1000 <= Node.val <= 1000

Follow-up:

You may only use constant extra space.

The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

풀이

은찬


const connect = (root) => {
    const answer = root;
    const pointer = root;
    const queue = [];
    const stack = [];
    let count = 1;
    
    if(!root){
        return root;
    }
    
    queue.push([pointer, 0]);
    
    while(queue.length){
        let [current, depth] = queue.shift();
        const left = current.left;
        const right = current.right;
        
        if(left){
            queue.push([left, depth + 1]);
        }
        
        if(right){
            queue.push([right, depth + 1]);    
        }
        
        if(count === Math.pow(2, depth)){
            current.next = null;
            
            while(stack.length){
                const node = stack.pop();
                
                node.next = current;
                current = node;
            }
            
            count = 0;
        } else{
            stack.push(current);
        }
        
        count++;
    }
    
    return answer;
};

재영

정리

같은 레벨에서의 순서를 배정해야 하므로, 깊이보다는 너비 우선 탐색(BFS)가 적합하다고 판단했습니다.

풀이 방법은 다음과 같습니다.

결국 노드 값을 반환해야 합니다. 따라서 return root로 기본 반환 값을 설정해주었습니다.

우리는 자바스크립트의 객체 타입은 call by reference임을 알고 있습니다. 따라서 이를 이용합니다. 큐에서는 length가 있을 때까지 내뱉어야 하는데, 이때 node.next로 변환해야 할 값은 큐에서 다음에 나올 노드여야 합니다. 만약 현재 나온 값이 마지막이면 null 처리를 그대로 해주면 되는 것입니다.

그렇다면 우리의 핵심 문제는 어떻게 레벨별로 큐를 만들어주느냐입니다. 이는 매우 간단하게, for문을 큐에서 하나 만들어주어, 같은 레벨에서만 큐를 처리할 수 있도록 하는 방법을 차용했습니다.

결과적으로 null일 때와, null이 아닌 경우에 대한 모든 경우의 수만 분기 처리해준다면 해결할 수 있습니다.


/**
 * // 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 === null) return root;

  const queue = [];
  queue.push(root);
  
  while (queue.length) {
      const length = queue.length;
      
      for (let i = 0; i < length; i += 1) {
          // call by reference를 이용하기 위해 다음과 같이 설정하였습니다.
          const node = queue.shift();
          
          if (i !== length - 1) {
              node.next = queue[0]
          }
          
          if (node.left !== null) {
              queue.push(node.left)
          }

          if (node.right !== null) {
              queue.push(node.right)
          }
      }
  }
  
  return root;
};

Populating Next Right Pointers in Each Node

풀이

정리