116. Заполнение правых указателей в каждом узле (Populating Next Right Pointers in Each Node)
Задание.
Вам дается идеальное двоичное дерево, где все листья находятся на одном уровне, и у каждого родителя есть два дочерних элемента. Двоичное дерево имеет следующее определение:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Заполняйте каждый следующий указатель так, чтобы он указывал на его следующий правый узел. Если следующего правого узла нет, следующему указателю должно быть присвоено значение NULL.
Изначально всем следующим указателям присваивается значение NULL.
Пример 1.
Входные данные: root = [1,2,3,4,5,6,7]
Результат: [1,#,2,3,#,4,5,6,7,#]
Объяснение: Получив приведенное выше идеальное двоичное дерево (рисунок A), ваша функция должна заполнить каждый следующий указатель, чтобы указывать на его следующий правый узел, точно так же, как на рисунке B. Сериализованный вывод находится в порядке уровней, соединенных следующими указателями, причем ‘#’ обозначает конец каждого уровня.
Пример 2.
Входные данные: root = []
Результат: []
Решение.
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() : val(0), left(NULL), right(NULL), next(NULL) {}
Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
Node* connect(Node* root) {
if(!root) return nullptr;
queue<Node*> q;
q.push(root);
while(size(q)) {
Node* rightNode = nullptr; // инициализация rightNode
for(int i = size(q); i; i--) { // прохождение каждого уровня
auto cur = q.front(); q.pop(); // извлечение текущего узла и
cur -> next = rightNode; // установка указателя на rightNode
rightNode = cur; // обновление rightNode для следующей итерации
if(cur -> right) // если есть потомки,
q.push(cur -> right), // помещаем в очередь, сначала правых
q.push(cur -> left); // затем левых
}
}
return root;
}
};