在针对“填充每个节点的下一个右侧节点指针 II”这类涉及链表和树结合的题目时，数据生成器的核心挑战在于：既要构造出各种稀疏、稠密、退化等形态的树，又要确保输出格式能有效验证 next 指针的正确性。

由于该题在 LeetCode 上的验证方式是查看连接后的 next 链表，我们的 .out 文件将采用“按层输出 next 指针指向的序列”来作为标准答案。

C++ 数据生成器与标程集成代码 (gen.cpp)

该程序会一次性生成 1.in/out 到 10.in/out。

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <ctime>
#include <random>

using namespace std;

// NOI 风格结构体定义
struct Node {
    int val;
    Node *left, *right, *next;
    Node(int x) : val(x), left(nullptr), right(nullptr), next(nullptr) {}
};

// --- [核心算法：最优 O(1) 空间填充 next 指针] ---
// 使用非递归迭代方式，避免爆栈
Node* connect(Node* root) {
    if (!root) return nullptr;
    Node* currLayerNode = root;
    while (currLayerNode) {
        Node dummy(-1);
        Node* tail = &dummy;
        while (currLayerNode) {
            if (currLayerNode->left) {
                tail->next = currLayerNode->left;
                tail = tail->next;
            }
            if (currLayerNode->right) {
                tail->next = currLayerNode->right;
                tail = tail->next;
            }
            currLayerNode = currLayerNode->next;
        }
        currLayerNode = dummy.next;
    }
    return root;
}

// --- [辅助工具：序列化与验证输出] ---

// 将树转换为 LeetCode 风格层序字符串
string serialize(Node* root) {
    if (!root) return "null";
    string res = "";
    queue<Node*> q;
    q.push(root);
    vector<string> vec;
    while (!q.empty()) {
        Node* curr = q.front();
        q.pop();
        if (curr) {
            vec.push_back(to_string(curr->val));
            q.push(curr->left);
            q.push(curr->right);
        } else {
            vec.push_back("null");
        }
    }
    // 剪枝：去除末尾多余的 null
    while (!vec.empty() && vec.back() == "null") vec.pop_back();
    for (size_t i = 0; i < vec.size(); ++i) {
        res += vec[i] + (i == vec.size() - 1 ? "" : " ");
    }
    return res;
}

// 遍历 next 指针以生成标准输出：每行代表一层
void writeOutput(Node* root, ofstream& fout) {
    if (!root) return;
    Node* levelStart = root;
    while (levelStart) {
        Node* curr = levelStart;
        Node* nextLevelStart = nullptr;
        while (curr) {
            fout << curr->val << (curr->next ? " " : "");
            // 寻找下一层第一个有效节点
            if (!nextLevelStart) {
                if (curr->left) nextLevelStart = curr->left;
                else if (curr->right) nextLevelStart = curr->right;
            }
            curr = curr->next;
        }
        fout << endl;
        // 如果当前行没找到下一层起点，遍历当前行其他节点的子节点
        if (!nextLevelStart) {
            Node* temp = levelStart;
            while (temp) {
                if (temp->left) { nextLevelStart = temp->left; break; }
                if (temp->right) { nextLevelStart = temp->right; break; }
                temp = temp->next;
            }
        }
        levelStart = nextLevelStart;
    }
}

// --- [造数逻辑：构建各种形态的树] ---

// 随机生成树
Node* genRandom(int n) {
    if (n <= 0) return nullptr;
    Node* root = new Node(rand() % 201 - 100);
    queue<Node*> q;
    q.push(root);
    int count = 1;
    while (count < n && !q.empty()) {
        Node* curr = q.front(); q.pop();
        if (count < n && rand() % 10 < 8) {
            curr->left = new Node(rand() % 201 - 100);
            q.push(curr->left); count++;
        }
        if (count < n && rand() % 10 < 8) {
            curr->right = new Node(rand() % 201 - 100);
            q.push(curr->right); count++;
        }
    }
    return root;
}

// 生成极端链状树 (Skewed)
Node* genSkewed(int n, bool leftOnly) {
    if (n <= 0) return nullptr;
    Node* root = new Node(rand() % 201 - 100);
    Node* curr = root;
    for (int i = 1; i < n; ++i) {
        if (leftOnly) { curr->left = new Node(rand() % 201 - 100); curr = curr->left; }
        else { curr->right = new Node(rand() % 201 - 100); curr = curr->right; }
    }
    return root;
}

// 生成“稀疏”的长腿树 (Sparse)
Node* genSparse(int n) {
    Node* root = new Node(1);
    Node* curr = root;
    for (int i = 1; i < n / 2; ++i) {
        curr->left = new Node(i * 2);
        curr->right = new Node(i * 2 + 1);
        // 故意让左右子树高度极度不平衡
        curr = (rand() % 2 == 0) ? curr->left : curr->right;
    }
    return root;
}

// --- [生成器主逻辑] ---
void make_test(int id, int n, string type) {
    string in_file = to_string(id) + ".in";
    string out_file = to_string(id) + ".out";
    ofstream fin(in_file), fout(out_file);

    Node* root = nullptr;
    if (type == "empty") root = nullptr;
    else if (type == "single") root = new Node(42);
    else if (type == "left_skewed") root = genSkewed(n, true);
    else if (type == "right_skewed") root = genSkewed(n, false);
    else if (type == "sparse") root = genSparse(n);
    else root = genRandom(n);

    // 1. 先写输入文件（序列化）
    fin << serialize(root) << endl;

    // 2. 执行标准程序（填充 next）
    root = connect(root);

    // 3. 写输出文件（验证 next）
    writeOutput(root, fout);

    cout << "Test #" << id << " [" << type << "] N=" << n << " done." << endl;
}

int main() {
    srand(time(0));
    make_test(1, 0, "empty");
    make_test(2, 1, "single");
    make_test(3, 15, "perfect_binary");
    make_test(4, 100, "left_skewed");
    make_test(5, 100, "right_skewed");
    make_test(6, 500, "sparse");
    make_test(7, 1000, "random");
    make_test(8, 3000, "random");
    make_test(9, 6000, "random");       // 满额数据规模
    make_test(10, 6000, "right_skewed");// 极限深度
    return 0;
}

数据说明与优化逻辑总结

1. 测试点分布 (Test Plan)

• Test 1-2: 最小规模边界（空树、单节点），防止程序对 root->left 直接解引用导致的 RE。
• Test 4-5: 极端退化树。验证 $O(1)$ 空间算法在“只有一条腿”的树中是否能正确切换到下一层。
• Test 6: 稀疏树。用于检测当某些层中间出现大面积 null 时，next 指针是否能正确跨越虚空连接到远方的右侧节点。
• Test 9-10: 满额规模（6000点）。测试算法的时间效率和深度。

2. 时间复杂度优化

• 生成阶段：使用了基于 queue 的 BFS 构造和 serialize，时间复杂度为 $O(N)$。由于 $N=6000$ 且 10 组数据，总计算量仅为 $6 \times 10^4$ 级别，运行时间极短（毫秒级）。
• 剪枝：在 serialize 函数中，末尾的 null 节点被手动切除，这符合 LeetCode 的紧凑序列化标准，且有效控制了输入文件的大小。

3. 空间复杂度与鲁棒性

• 内存控制：单个最大文件大约为 $6000 \times 6$ 字节 $\approx 36\text{KB}$。10 组数据总大小远低于 2MB。
• 非递归遍历：connect 函数和 writeOutput 均采用指针迭代法（利用已有的 next），完全避免了在处理深度为 6000 的退化树时可能出现的栈溢出（Stack Overflow）。
• 异常防护：在 writeOutput 中，通过 while(temp) 循环二次检查下一层起点，确保即使当前节点的子节点全为空，也能正确找到当前层后续节点的子节点。

4. 理解题意的关键词

在 OJ 读题或调试时，请关注：

• "Populating"：意味着这是原地修改题。
• "Next"：必须在层序遍历的过程中建立联系。
• "O(1) space"：暗示你必须利用已经建立好的 next 指针，将当前层视作一个链表来移动，而不是存入队列。

在 NOI 竞赛中，内存限制（Memory Limit）通常是 256MB 或 512MB，但在处理百万级数据或复杂树形结构时，优化空间复杂度至 $O(1)$ 往往是区分省一与省二的关键。

本题我们从最稳健的 BFS 做法开始，逐步优化到 $O(1)$ 额外空间的满分做法。

版本一：标准队列 BFS（竞赛中最稳的保底方案）

思路思考： 利用 std::queue 进行层序遍历。在处理每一层时，将当前节点的 next 指向队列中的下一个节点（注意最后一节点指向 NULL）。这是最容易想到的方案，逻辑简单，不易出错。

由于使用了标准的 std::queue，它自动处理了树的各种奇葩形状（如只有左子树、只有右子树、非常稀疏等），你不需要手动写复杂的指针查找逻辑

复杂度分析：

• 时间：$O(N)$，每个节点进出队各一次。
• 空间：$O(N)$，队列最大长度取决于树的最大宽度。

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <sstream>

using namespace std;

// 1. 结构体定义
struct Node {
    int val;
    Node *left, *right, *next;
    // 构造函数：初始化时 next 必须设为 nullptr
    Node(int x) : val(x), left(nullptr), right(nullptr), next(nullptr) {}
};

/**
 * 版本一：BFS 队列法
 * 思路：利用队列记录每一层的节点，在出队处理时，将前一个节点的 next 指向当前节点。
 */
Node* connect(Node* root) {
    if (!root) return nullptr;

    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        int sz = q.size(); // 易错点：必须提前固定当前层的大小
        Node* prev = nullptr;

        for (int i = 0; i < sz; ++i) {
            Node* curr = q.front();
            q.pop();

            // 如果 prev 不为空，说明 curr 是 prev 的右侧邻居
            if (prev) {
                prev->next = curr;
            }
            prev = curr; // 更新 prev

            // 标准 BFS：左孩子先入队，右孩子后入队
            if (curr->left) q.push(curr->left);
            if (curr->right) q.push(curr->right);
        }
        // 循环结束时，本层最后一个节点的 next 保持为 nullptr
    }
    return root;
}

// 2. 辅助函数：根据层序字符串构建树 (处理 null)
Node* buildTree(string data) {
    if (data.empty()) return nullptr;
    stringstream ss(data);
    string item;
    if (!(ss >> item) || item == "null") return nullptr;

    Node* root = new Node(stoi(item));
    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        Node* curr = q.front();
        q.pop();

        if (!(ss >> item)) break;
        if (item != "null") {
            curr->left = new Node(stoi(item));
            q.push(curr->left);
        }

        if (!(ss >> item)) break;
        if (item != "null") {
            curr->right = new Node(stoi(item));
            q.push(curr->right);
        }
    }
    return root;
}

// 3. 辅助函数：严格按照样例格式输出
void printForOJ(Node* root) {
    if (!root) return;

    Node* levelStart = root; // 每一层的第一个节点
    while (levelStart) {
        Node* curr = levelStart;
        Node* nextLevelStart = nullptr;
        bool first = true;

        while (curr) {
            if (!first) cout << " ";
            cout << curr->val;
            first = false;

            // 在当前层寻找下一层的第一个有效节点（左孩子优先，没有则找右孩子）
            if (!nextLevelStart) {
                if (curr->left) nextLevelStart = curr->left;
                else if (curr->right) nextLevelStart = curr->right;
            }
            curr = curr->next; // 沿着 next 指针横向移动
        }
        cout << "\n";

        // 如果在当前层的所有节点都没找到孩子，需要继续往下游找
        // 但在 BFS 填充好的情况下，只需移动到刚才找到的 nextLevelStart
        levelStart = nextLevelStart;
    }
}

int main() {
    // 提高 IO 效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string input;
    if (getline(cin, input) && !input.empty()) {
        Node* root = buildTree(input);
        
        // 执行核心逻辑
        root = connect(root);
        
        // 按照 OJ 要求格式输出
        printForOJ(root);
    }

    return 0;
}

版本二：最优复杂度 $O(1)$ 空间做法（金牌选手思路）

思路思考： 既然题目已经给了我们 next 指针，为什么不直接利用它呢？

• 当我们处理第 $H$ 层时，第 $H-1$ 层已经通过 next 指针连成了一个单链表。
• 我们可以像遍历单链表一样遍历 $H-1$ 层，同时根据它们的左右子节点来“缝合”第 $H$ 层的 next 指针。
• 技巧：使用一个 dummy（虚拟头节点）来代表下一层的起点，这样就不需要判断谁是下一层的第一个有效节点了。

复杂度分析：

• 时间：$O(N)$，每个节点被扫描常数次。
• 空间：$O(1)$，仅使用了三个辅助指针。

#include <iostream>
#include <queue>
#include <string>
#include <sstream>

using namespace std;

// 1. 结构体定义
struct Node {
    int val;
    Node *left, *right, *next;
    Node(int x) : val(x), left(nullptr), right(nullptr), next(nullptr) {}
};

/**
 * 版本二：$O(1)$ 空间指针迭代法
 * 思路：利用每一层已有的 next 指针进行横向遍历，同时用一个 dummy 节点连接下一层。
 */
Node* connect(Node* root) {
    if (!root) return nullptr;

    Node* currLayerHead = root; // 当前层的起点

    while (currLayerHead) {
        // 关键点：为下一层创建一个虚拟头节点 (Dummy)
        // 使用局部变量，保证每一层都是全新的开始
        Node dummy(-1); 
        Node* tail = &dummy; // tail 始终指向下一层当前已缝合的最后一个节点

        // 像遍历链表一样遍历当前层
        Node* p = currLayerHead;
        while (p) {
            // 如果有左孩子，接上，tail 后移
            if (p->left) {
                tail->next = p->left;
                tail = tail->next;
            }
            // 如果有右孩子，接上，tail 后移
            if (p->right) {
                tail->next = p->right;
                tail = tail->next;
            }
            // 借助上一层已经连好的 next 指针向右走
            p = p->next;
        }

        // 当前层处理完后，下一层的起点就是 dummy.next
        currLayerHead = dummy.next;
    }
    return root;
}

// --- 辅助函数：构建树 (适配 OJ 输入格式) ---
Node* buildTree(string data) {
    if (data.empty()) return nullptr;
    stringstream ss(data);
    string item;
    if (!(ss >> item) || item == "null") return nullptr;

    Node* root = new Node(stoi(item));
    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        Node* curr = q.front();
        q.pop();

        if (!(ss >> item)) break;
        if (item != "null") {
            curr->left = new Node(stoi(item));
            q.push(curr->left);
        }

        if (!(ss >> item)) break;
        if (item != "null") {
            curr->right = new Node(stoi(item));
            q.push(curr->right);
        }
    }
    return root;
}

// --- 辅助函数：输出 (严格匹配样例格式) ---
void printForOJ(Node* root) {
    if (!root) return;

    Node* levelStart = root;
    while (levelStart) {
        Node* curr = levelStart;
        Node* nextLevelStart = nullptr;
        bool first = true;

        while (curr) {
            if (!first) cout << " ";
            cout << curr->val;
            first = false;

            // 顺便寻找下一层的物理起点
            if (!nextLevelStart) {
                if (curr->left) nextLevelStart = curr->left;
                else if (curr->right) nextLevelStart = curr->right;
            }
            curr = curr->next;
        }
        cout << "\n";
        levelStart = nextLevelStart;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string input;
    if (getline(cin, input) && !input.empty()) {
        Node* root = buildTree(input);
        root = connect(root);
        printForOJ(root);
    }

    return 0;
}

1. 时间复杂度：$O(N)$

• 思考过程：
  • 外层 while 循环遍历树的深度 $H$。
  • 内层 while 循环遍历每一层的节点数 $W_i$。
  • 由于 $\sum W_i = N$，即每个节点只会被扫描常数次（一次作为当前层，一次作为下一层被连接）。
  • 结论：时间复杂度是线性的。

2. 空间复杂度：$O(1)$

• 思考过程：
  • 在这个版本中，我们没有使用 std::queue 或任何递归。
  • 我们只使用了 currLayerHead, dummy, tail, p 这几个指针。
  • 无论树有多少节点、深度有多大，这些辅助变量所占的内存是固定的。
  • 结论：这是最优空间解法。

3. 优化建议：为什么使用 Dummy 节点？

如果不使用 dummy 节点，代码会变得非常繁琐：

1. 你需要判断下一层的第一个节点在哪里（可能是左孩子，也可能是右孩子，甚至前几个节点都没子节点）。
2. 你需要一个额外的变量来保存下一层的头。
3. Dummy 的妙处：它像一根“挂钩”，无论下一层第一个节点在哪里，直接挂在 dummy.next 上即可，处理完一层后，通过 dummy.next 就能立刻找到下一层的入口。

读题关键词与易错点总结

1. 关键词：

   • "Next Right"：意味着我们要建立水平方向的联系。
   • "Populating"：意味着在原有的数据结构上修改。
   • "Constant Space"：直接排除 BFS 队列。

2. 易错点：

   • 空层情况：如果某一层一个子节点都没有（比如你是叶子层），dummy.next 会是 nullptr，此时 currLayerHead 变为 nullptr，循环正确终止。
   • Dummy 作用域：Node dummy(-1) 放在外层 while 循环内，这样每一层开始时 dummy.next 都是 nullptr，防止把旧的链接带到新的一层。
   • 非完全二叉树：一定要用 while(p) 遍历完整层，因为当前节点的邻居可能没有孩子，但邻居的邻居可能有孩子，必须跨过去连接。

七、 总结：读题关键词与易错点

1. 读题关键词：

   • “Next Right Pointer”：暗示了结构具有“层”的属性。
   • “Any binary tree”：与“Perfect binary tree”不同，这说明不能简单地连接 left->next = right，因为中间可能有空缺，必须动态寻找下一个节点。
   • “O(1) extra space”：排除所有使用 std::queue 或 std::vector 的方案，也间接排除了深层递归（递归栈空间）。

2. NOI 考场易错点：

   • Dummy 节点的生命周期：在版本二中，dummy 必须在每一层循环开始时重置或重新创建，否则会导致多层节点串联在一起。
   • 下一层起点的寻找：如果不用 dummy 节点，代码会变得极其臃肿，因为你需要处理本层第一个有子节点的节点作为下一层的 head，非常容易漏掉某种情况。
   • 空指针解引用：在执行 tail->next = ... 之前，必须确保 tail 已经被初始化，且该层确实有节点。

时间复杂度优化建议：

• 虽然 $O(N)$ 已经是理论下限，但在大规模数据下（$N > 10^5$），减少指针跳转（Cache Miss）会有帮助。
• 版本二的迭代法比版本一的队列法更快，因为它减少了 std::queue 的内存申请和释放操作。
• 在 NOI 中，尽量使用 \n 而非 endl 以避免频繁刷新缓冲区。