利用层序遍历，每次都保存上一个节点指针。当且仅当prev不为null才更新next

cpp
#include <queue>

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

Node* connect(Node* root) {
    if (root == nullptr) {
        return nullptr;
    }

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

    while (!q.empty()) {
        int levelSize = q.size();
        Node* prev = nullptr;

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

            if (prev != nullptr) {
                prev->next = node;
            }

            prev = node;

            if (node->left != nullptr) {
                q.push(node->left);
            }
            if (node->right != nullptr) {
                q.push(node->right);
            }
        }
    }

    return root;
}