LeetCode 117(Populating Next Right Pointers in Each Node II )

1. 문제 링크

• https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

2. 문제 설명

• 아래 형태의 binary tree가 주어졌을 때

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

• 각 next pointer를, 해당하는 다음 오른쪽 노드를 가리키도록 채워서 root 반환 
  • 여기서 다음 오른쪽 노드가 없는 경우, next pointer는 NULL로 설정이 되어야 하며,
  • 초기에는 모든 next 포인터가 NULL로 설정이 됨
• 직전 문제인 "Populating Next Right Pointers in Each Node"와의 차이는, 
  • 직전 문제는 complete binary tree (모든 level의 노드에서 left, right 노드가 채워져있는 트리)였고,
  • 해당 문제는 그냥 binary tree라는 점 
• 아래 예시 처럼 아래와 같은 binary tree가 주어지면,
  • root = [1,2,3,4,5,null,7]
  • 반환되는 root는 [1,#,2,3,#,4,5,7,#]이 된다.
  • node 1은 next가 존재하지 않으므로 NULL이 되고 (편의상 #로 찍히게 둔 것 같음)
  • node 2의 next 는 3, 3의 next는 존재하지 않으므로 NULL
  • node 4의 next 는 5, 5의 next는 7, 7의 next는 존재하지 않으므로 NULL이 된다.

 

3. 처음 풀이 

• 이전 문제에서는, cur.next가 존재하면
  • cur.right.next = cur.next.left 규칙이 성립이 되서, 
  • while문으로 코드 작성이 가능했는데,
• 해당 문제에서는 비어있는 node가 존재하기 때문에, 뭔가 복잡하게 느껴졌다.
• 그래서 예전에 풀었던, 전위 순회 식으로 각 node를 list에 쌓아가면서, 이전 node의 next에 현재 node를 연결해주는 식으로 코드를 작성하였다. 
• runtime이나, memory가 둘다 90%정도로 나쁘지 않게 나오긴 했는데,
• list를 만들어서, 이전 node 정보를 쌓고 있으니, node의 개수가 많아지면 메모리적으로 비효율적일것 같은 생각이 들었다. 
• 그래서 그냥 직전 node의 값만 특정 변수에 저장하는 방식으로 하려 했으나, 
  • level이 달라진다는 구분자를 아래 코드에서는 list의 element 개수로 잡았어서, 수정이 어려웠다...

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        
        result = []

        def helper(root, level): 
            if not root:
                return
            
            if len(result) < level: 
                result.append([root])
            else:
                result[level-1][-1].next = root 
                result[level-1].append(root)
            
            helper(root.left,level+1)
            helper(root.right,level+1)
        
        helper(root,1)

        return root

 

4. 다른 풀이

• 여기서는 deque를 사용하면서, tree의 해당 level에서의 개수를 알 수 있게 되고, 
  • 해당 개수만큼 같은 level안에서 for문을 돌리면서, next 관계를 이어가는 식으로 코드가 작성되어 있다.
  • 이전의 값을 저장해두는 prev라는 변수를 두고,
  • q에 쌓아둔 node 중 가장 왼쪽 값을 pop하면서, 
    • 그 값이 left node가 존재할 경우, 
      • 그 값을 q에 append를 하고, 
      • 이전의 node의 next에 popped.left를 연결해주고, 
      • prev는 한칸 next로 이동시킨다.
    • 그 값이 right node가 존재할 경우, 마찬가지로
      
      • q에 해당 값을 append하고, 
      • 이전 node의 next에 popped.right를 연결해주고,
      • prev는 next로 이동시킨다. 

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None
        q = deque()
        q.append(root)
        dummy=Node(-999) # to initialize with a not null prev
        while q:
            length=len(q) # find level length
            
            prev=dummy
            for _ in range(length): # iterate through all nodes in the same level
                popped=q.popleft()
                if popped.left:
                    q.append(popped.left)
                    prev.next=popped.left
                    prev=prev.next
                if popped.right:
                    q.append(popped.right)
                    prev.next=popped.right
                    prev=prev.next                
                 
        return root

 

5. 배운 점

• deque활용