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

Problem

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,#]
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: []

Constraints:

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

---

Solution

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        Queue<Node> queue = new LinkedList<Node>();
        if (root == null)
            return root;
        queue.offer(root);
        while (queue.size() != 0) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                if (queue.peek() != null) {
                    queue.offer(queue.peek().left);
                    queue.offer(queue.peek().right);
                } else
                    return root;
                if (i == levelSize - 1) {
                    queue.poll();
                    break;
                }
                queue.poll().next = queue.peek();
            }
        }
        return root;
    }
}

Explanation

• 문제에서 요구하는 알고리즘은 어느 한 노드의 포인터에 오른쪽 노드를 할당하는 작업을 n층에서 수행하고, n + 1층으로 넘어가서 반복적으로 수행하는 것이다.
• n층에서 포인터를 연결하는 작업을 수행할 시, n + 1층의 노드들이 순서대로 대기하고 있으면 알고리즘을 좀 더 쉽게 작성할 수 있다. 노드들이 순차적으로 대기하는 자료구조로 Queue를 떠올릴 수 있다.
• 노드들이 대기할 자료구조로 Queue를 선언하고, root노드를 삽입한다.

  Queue<Node> queue = new LinkedList<Node>();
  queue.offer(root);
  

• 포인터를 연결하는 반복 작업을 수행하기 위해 for 반복문을 작성한다.
• for 반복문이 회전하는 횟수는 Queue에 들어있는 노드의 수가 된다. 그런데 for 반복문의 조건식에 직접 Queue의 크기를 사용하면 반복이 수행되는 동안 조건식이 변경되므로 for 반복문의 바깥에 Queue의 사이즈를 변수에 할당해 사용한다.
• n층의 가장 오른쪽 노드는 포인터에 할당해줄 필요가 없으므로 if 조건문을 선언하여 가장 오른쪽 노드는 포인터 할당 작업을 하지 않도록 한다.

  int levelSize = queue.size();
  // n층에서의 포인터 할당 반복작업
  for (int i = 0; i < levelSize; i++) {
    if (i == levelSize - 1) {
        queue.poll();
        break;
    }
    queue.poll().next = queue.peek();
  }
  

• n + 1층의 노드들을 Queue에 담는 if 조건문을 작성한다. 파라미터로 주어진 root노드는 완전 이진트리의 뿌리이므로, n + 1층의 노드에서 Null이 발견될 경우 더이상 비교를 진행할 필요가 없으므로 root노드를 반환하도록 한다.

  if (queue.peek() != null) {
    queue.offer(queue.peek().left);
    queue.offer(queue.peek().right);
  } else
    return root;
  

• n층에서 포인터 할당 작업을 완료했으면 다음 층으로 내려가 반복적으로 작업을 수행해야 하므로 while 반복문을 작성한다.

  // n층에서 다음 층으로 내려가는 반복 작업
  while (queue.size() != 0) {
    int levelSize = queue.size();
    // n층에서의 포인터 할당 반복작업
    for (int i = 0; i < levelSize; i++) {
        if (queue.peek() != null) {
            queue.offer(queue.peek().left);
            queue.offer(queue.peek().right);
        } else
            return root;
        if (i == levelSize - 1) {
            queue.poll();
            break;
        }
        queue.poll().next = queue.peek();
    }
  }
  

• 반환 문장이 없어도 문제가 해결될 것으로 보이지만, 제출이 되지 않아 반환문을 작성한다.

  return root;