Leetcode: Populating Next Right Pointers in each Node II
Given a tree, compute next for each node such that each node points to its next
neighbor to the right.
The idea is to have two alternate lists, curr_level and next_level. While travsering
the current level, all sub nodes (left and right) are written to next_level. After
all nodes are popped from the curr_level, set curr_level = next_level and begin the
process anew. This keeps track of the individual levels. Initially, set the curr_level
to [root].
"""
# 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 root is None:
return root
curr_level = [root]
while len(curr_level) > 0:
next_level = []
while len(curr_level) > 0:
node = curr_level.pop(0)
if len(curr_level) > 0:
node.next = curr_level[0]
if node.left is not None:
next_level.append(node.left)
if node.right is not None:
next_level.append(node.right)
curr_level = next_level
return root