Solution to LeetCode 116 Populating Next Right Pointers in Each Node and LeetCode 117 Populating Next Right Pointers in Each Node II.
LeetCode 116
Populating Next Right Pointers in Each Node (Medium) [link]
Level-order traversal plus a conditional next pointer addition. Time complexity O(n).
"""
# 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: 'Optional[Node]') -> 'Optional[Node]':
if not root: return None
que = deque([root])
while que:
size = len(que)
for i in range(size):
first = que.popleft()
if i == size - 1:
first.next = None
else:
first.next = que[0]
if first.left:
que.append(first.left)
if first.right:
que.append(first.right)
return root
LeetCode 117
Populating Next Right Pointers in Each Node II (Medium) [link]
Exactly the same as LC 116 because of level-order traversal. Time complexity O(n).
"""
# 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':
if not root:
return None
que = deque([root])
while que:
size = len(que)
for i in range(size):
first = que.popleft()
if i == size-1:
first.next = None
else:
first.next = que[0]
if first.left:
que.append(first.left)
if first.right:
que.append(first.right)
return root
