Следующий правый указатель в каждой вершине дерева

 Дано бинарное дерево:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Заполнить поле next так, чтобы вершина дерева указывала на соседнюю вершину справа, если та существует. Если же никакой вершины справа не существует, то указательnext принимает значение NULL.

Изначально все next указатели имеют значение NULL.

Ограничение: можно использовать константный объём (не зависящий от размера лерева) дополнительной памяти.

Пример:

Дано: root = [1,2,3,4,5,null,7]
Результат: [1,#,2,3,#,4,5,7,#]
Объяснение: Исходное бинарное дерево на рисунке A. Результат на рисунке B: каждая вершина указывает на соседа справа, если он существует. А если не существует, то указывает на NULL. Сериализованный результат выведен в порядке уровней дерева, где уровни разделены символом #. Внутри уровня его элементы указаны слева направо.

Идея решения

Нам нужно обойти все "этажи" дерева и выстроить в цепочку элементы дерева, находящиеся на одном "этаже". Самый правый элемент будет указывать на NULL.

Находясь в вершине (root) дерева, мы знаем, что у него есть (возможно нулевые) левое и правое поддеревья. Между ними мы можем легко выстроить цепочку: левое указывает на правое, правое указывает на null. И тыкже мы можем знать, где находится начало этажа: в вершине левого поддерева - это голова цепочки.

Если взять наш пример, то цепочка первого (не корневого) этажа будет иметь вид: (голова)2->3->null

Затем мы переходим к следующему этажу, на котором уже все элементы выстроены в цепочку. Мы берем голову цепочки и проходим по ее элементам, строя цепочку следующего этажа, то есть глядя поддеревья. Опять-таки, у дерева в корне 2 мы выстраиваем его поддеревья в цепочку второго этожа 4->5. Затем переходим к поддереву 3 и продолжаем цепочку второго этажа так, чтобы она приняла вид: (голова)4->5->7. При этом 7 будет указывать на пустой элемент.

Итеративно переходим к следующему этажу. Если у него нет поддеревьев ни в каком элементе, мы не можем построить следующий этаж и завершаем обход дерева.

Имплементация решения

public Node connect(Node root) {
        Node head = null; // начало следующего уровня
        Node prev = null; // предыдущий элемент уровня
        Node cur = root;  //текущий элемент уровня, начинаем с root

        while (cur != null) { //  пока существую элементы
            
            while (cur != null) { // итерация по "этажу"
                //сушествует ли элемент слева
                if (cur.left != null) {
                    // если начали строить цепочку, то ее следующий элемент
                    // указывает на то, что есть (левый текущего)
                    if (prev != null) {
                        prev.next = cur.left;
                    } else { // ещё не начали строить цепочку
                        // cur.left - самый левый элемент "этажа",
                        // запоминаем его, как "голову этажа"
                        head = cur.left;
                    }
                    // строим цепочку из того, что есть, то есть из левого элемента от текущего
                    prev = cur.left;
                }
                //существует ли элемент справа
                if (cur.right != null) {
                    if (prev != null) {
                        // если начали строить цепочку, то ее следующий элемент
                        // указывает на то, что есть (правыйтекущего)
                        prev.next = cur.right;
                    } else { // ещё не начали строить цепочку
                        // cur.right- самый левый элемент "этажа",
                        // запоминаем его, как "голову этажа"
                        head = cur.right;
                    }
                     // строим цепочку из того, что есть, то есть из правого элемента от текущего
                    prev = cur.right;
                }
                // переходим к следущему элементу этажа
                cur = cur.next;
            }
            
            // если дошли до конца этажа (cur==NULL), то переходим на следующий этаж,
            // для этого используем "голову" следующего этажа, а это хранится в head
            cur = head;
            head = null;
            prev = null;
        } // обошли все элементы
        return root;
    }