Leetcode # 116. Populating Next Right Pointers in Each Node

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

Solution

使用BFS，使上層的 node 得以被優先處理

如果 cur.next 存在 ⇒ 說明 cur 同一層中還有右節點
⇒ cur.right.next = cur.next.left

class Solution:
  def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
    if root is None:
      return root
    queue = collections.deque([root])
    while queue:
      cur = queue.popleft()
      if cur.left is not None:
        cur.left.next = cur.right
        queue.append(cur.left)
        queue.append(cur.right)
        if cur.next is not None:
          cur.right.next = cur.next.left
        
    return root

Refined Solution

使用一縱一橫的 pointer 取代 BFS
能使得 space complexity 從 O(n) 縮減至 O(1)

class Solution:
  def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
    layer_start = root
    while layer_start:
      cur = layer_start
      while cur:
        if cur.left is not None:
          cur.left.next = cur.right
          if cur.next is not None:
            cur.right.next = cur.next.left
        cur = cur.next
      layer_start = layer_start.left
        
    return root

Last Updated on 2023/08/16 by A1go