LeetCode: 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.

 

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, 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.

이 문제는 처음에 좀 당활을 할 수 있는 문제이다. 

 

하지만 문제를 잘 읽어보면 어떻게 풀이를 해야 할 지 알 수 있게 된다. 

 

일단 그래프의 next가 None으로 초기화가 되어있다는 것을 잘 알고 있어야 한다. 

 

그리고 이 문제는 return값이 무엇이 되어야 하는지 작성되어 있지 않아 고생을 했다. 

 

결국 next의 pointer가 같은 층의 노드를 가르키고 있어야 하고 가장 오른쪽 노드는 None을 가르키게 하면 된다.

 

그래서 어떻게 해야할까?

 

이 문제는 속임수가 있는 것 같다. 

 

DFS 문제 항에 있지만 BFS로 푸는게 좀 더 합리적으로 보이기 때문이다. 

 

BFS로 푸는 이유는 완전이진트리를 방문할 때, 같은 층에 대해서 next 의 pointer를 지정하는게 수월하기 떄문이다.

 

풀이 순서는 다음과 같다. 

 

1. deque를 사용하여 큐를 구성한다. 

2. queue에 root노드를 넣는다. 

3. queue가 있을 때까지 while문안의 코드를 반복한다. 

4. prev(이전 노드)를 None으로 초기화 시킨다.

5. for i in range(len(queue)): 를 놓는다. -> 한 층을 전부 돌면서 노드를 queue에 추가시키는 과정을 하는데 이 과정을 len만큼 하면 다음 층의 노드들만 queue에 추가가 되기 때문에 이 방식을 사용함

 

6. prev가 있다면 prev.next의 값을 queue.popleft() (현재노드)의 값으로 놓는다. -> 같은 층의 노드

7. prev를 현재 노드로 지정 -> 이러면 다음 반복에 prev가 있고 현재 노드.next가 다음 탐색노드가 되면서 문제의 조건을 만족하게 된다. 

 

8. for문을 빠져나온 뒤에는 prev를 None으로 설정하여 층을 분리한다. 

 

나는 마지막에서 Next를 어떻게 null로 구할까? 이게 의문이었다.

 

하지만 Next는 모두 None으로 초기화되어 있다. 따라서 그냥 놔두면 null값이라고 판단하는 것이었다.

 

 

문제가 불친절하다 불친절해..

 

참고로 시작에 root부터 없으면 그냥 None을 반환했다.

 

---

 

구현코드

 

from collections import deque
"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution(object):
    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if not root:
            return None

        queue = deque([root])

    
        
        while queue:
            prev = None
            for i in range(len(queue)):
                node = queue.popleft()

                if prev:
                    prev.next = node
                    
                prev = node

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            prev = None
        
        return root