Bfs

#include <queue>

void ConnectNext(TreeNode* root) {
    if (!root) return;

    std::queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int levelSize = q.size(); // Количество узлов на текущем уровне
        TreeNode* prev = nullptr;

        for (int i = 0; i < levelSize; ++i) {
            TreeNode* current = q.front();
            q.pop();

            // Связываем предыдущий узел с текущим
            if (prev) {
                prev->next = current;
            }
            prev = current;

            // Добавляем дочерние узлы в очередь
            if (current->left) q.push(current->left);
            if (current->right) q.push(current->right);
        }

        // Последний узел уровня указывает на nullptr
        if (prev) {
            prev->next = nullptr;
        }
    }
}