116. Populating Next Right Pointers in Each Node

116. Populating Next Right Pointers in Each Node

문제

완전 이진 트리에서 next 포인터에 동일 레벨의 인접한 다음 노드를 추가하는 문제이다.

• 형제 노드의 경우
  node.left.next = node.right
• 부모 노드가 다른 동일 레벨의 노드인 경우
  node.right.next = node.next.left
• next 포인터가 없으면 null

트리의 구조 및 용어 설명은 👉 여기

테스트 케이스

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

next 포인터가 null일 경우 '#'로 나타낸 것

👉 output의 형태는 신경쓰지 않고, next 포인터를 채우는 함수를 완성한다.

풀이

핵심은 node의 left를 탐색하는 leftEnd와 next를 연결하는 curr이다. leftEnd는 트리의 마지막 레벨에 도달할 때까지 각 레벨을 반복하고 curr는 동일 레벨(자식)의 다음 노드를 next 포인터로 연결한다. 코드를 보는 편이 이해가 쉬울 것 같다.

Depth 탐색하는 leftEnd

// 코드 일부
let leftEnd = root;
while (leftEnd.left) {
  
  // ... 중략 ...
  
  leftEnd = leftEnd.left;
}

leftEnd의 역할은 left 포인터가 있을 때까지 반복한다. 마치 이중 반복문에서 행을 탐색하는 것과 같다.

next포인터를 연결하는 curr

// 코드 일부
let curr = leftEnd;
while (curr) {
  curr.left.next = curr.right;
  if (curr.next) {
    curr.right.next = curr.next.left;
  }
  curr = curr.next;
}

• leftEnd 노드를 node로 담고 node.next가 있을 때까지 반복한다.
• 먼저 형제노드의 next 포인터를 연결한다.
  curr.left.next = curr.right
• node.next가 있으면 (부모노드의 형제노드)
  curr.right.next = curr.next.left
• 이전에 연결한 자신의 next가 있다면, next로 이동한다.

전체 코드

/**
 * // 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;

  let leftEnd = root

  while(leftEnd.left) {
    let curr = leftEnd;
    while(curr) {
      curr.left.next = curr.right;
      if (curr.next) {
        curr.right.next = curr.next.left;
      }
      curr = curr.next;
    }
    leftEnd = leftEnd.left;
  }

  return root
};