Leetcode: Populate next pointers in tree
Given a perfect binary search tree, connect all the nodes to the node on their right
The solution is to do breadth-first-search in an iterative fashion. This puts all the nodes at the same level in a queue. By iterating over the queue we can connect each node to its successor. During this process we add the children of each node as the next entry. We repeat this process until the queue is empty.
class Node:
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
def __repr__(self) -> str:
return f'{self.val}'
class Solution:
def connect(self, root):
queue = [[root]]
while len(queue) > 0:
for i in range(len(queue[0]) - 1):
queue[0][i].next = queue[0][i+1]
queue.append([])
for i in range(len(queue[0])):
item = queue[0][i]
if item.left is not None:
queue[-1].append(item.left)
if item.right is not None:
queue[-1].append(item.right)
if len(queue[-1]):
queue.pop()
queue = queue[1:]
return root
if __name__ == '__main__':
s = Solution().connect
r = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), Node(7)))
s(r)
Runtime: 84 ms, faster than 70.50% of Python3 online submissions for Populating Next Right Pointers in Each Node. Memory Usage: 15.8 MB, less than 49.85% of Python3 online submissions for Populating Next Right Pointers in Each Node.