Задача 9: Заполнение указателей следующего права в каждом узле

Напишите определение функции connect(root), которая принимает корень идеально сбалансированного бинарного дерева root типа Node и изменяет дерево так, чтобы указатели next каждого узла указывали на его соседний узел справа. Если такого узла не существует, указатель next должен указывать на None.

Дерево описывается с помощью объекта Node, который имеет следующие свойства:

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

• val: значение узла (целое число).
• left: ссылка на левый дочерний узел.
• right: ссылка на правый дочерний узел.
• next: ссылка на следующий узел справа.

Особенности:

1. Дерево является идеально сбалансированным, то есть все листья находятся на одном уровне, и у каждого родителя есть ровно два потомка.
2. Изначально все указатели next равны None.

Пример 1:

Входные данные:

root = [1, 2, 3, 4, 5, 6, 7]

Дерево выглядит следующим образом:

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

Выходные данные:

[1,#,2,3,#,4,5,6,7,#]

Схема дерева после выполнения функции:

        1 -> NULL
      /   \
     2  -> 3 -> NULL
    / \   / \
   4->5->6->7 -> NULL

Обозначение:

• -> указывает на следующий узел, на который должен указывать указатель next.
• NULL обозначает отсутствие следующего узла справа.

Пример 2:

Входные данные:

root = []

Выходные данные:

[]

Объяснение: Дерево пустое, никаких изменений не требуется.

Как использовать объект Node:

1. Объект Node скрытно заготовлен в коде, и при решении задачи предполагается, что он уже существует.

2. Для работы с деревом можно создавать узлы с помощью конструктора, например:

   root = Node(1)
   root.left = Node(2)
   root.right = Node(3)
   

3. После выполнения функции connect, дерево будет модифицировано в месте, где next-ссылки узлов будут правильно установлены.