// 演算法 / Algorithm:
// 一層一層往下處理。處理某一層時，該層的 next 已經串好，形成一條鏈；
// 沿著這條鏈走，用 dummy+tail 把下一層的孩子（先左後右）接成新的一條鏈。
// 只用幾個指標變數，達到 O(1) 額外空間。
// Process level by level. When at a level, its next-chain is already built;
// walk that chain and, with dummy+tail, thread this level's children into the
// next level's chain. Uses only a few pointers → O(1) extra space.

struct Node* connect(struct Node* root) {
    // cur 指向「目前正在處理的那一層」的最左節點，一開始就是根
    // cur points to the leftmost node of the level we're processing; start at root
    struct Node* cur = root;

    // 只要還有下一層要處理就繼續（cur 為 NULL 代表沒有節點了）
    // Keep going while there is a level to process (cur == NULL means we're done)
    while (cur != NULL) {

        // dummy 是虛擬頭節點：它的 next 會指向「下一層的第一個節點」
        // 用它可以免去「第一個孩子要特別處理」的麻煩
        // dummy is a placeholder head; dummy.next will point to the next level's first node,
        // sparing us any special-case handling for the very first child
        struct Node dummy;
        dummy.next = NULL;        // 先清空，避免用到未初始化的垃圾值 / clear it to avoid garbage

        // tail 永遠指向「下一層鏈的目前尾巴」，一開始就是 dummy 本身
        // tail always points to the current tail of the next level's chain, starting at dummy
        struct Node* tail = &dummy;

        // 沿著目前這一層的 next 鏈，從左到右走訪每個節點 node
        // Walk the current level left-to-right along its next chain
        for (struct Node* node = cur; node != NULL; node = node->next) {

            // 如果 node 有左孩子，就把左孩子接到鏈尾，並讓 tail 前進
            // If node has a left child, append it and advance tail
            if (node->left != NULL) {
                tail->next = node->left;   // 接上 / link it
                tail = node->left;         // tail 前進到新尾巴 / tail moves forward
            }

            // 如果 node 有右孩子，同樣接到鏈尾，並讓 tail 前進
            // If node has a right child, append it and advance tail
            if (node->right != NULL) {
                tail->next = node->right;  // 接上 / link it
                tail = node->right;        // tail 前進 / tail moves forward
            }
        }

        // 這一層走完了。tail->next 目前是垃圾，明確設成 NULL 當作下一層的結尾
        // Level finished. tail->next is stale; set it to NULL as the next level's terminator
        tail->next = NULL;

        // 跳到下一層的第一個節點，繼續下一輪
        // Jump to the next level's first node and loop again
        cur = dummy.next;
    }

    // 回傳原本的根節點（結構已就地被修改好）/ return the (now-modified) root
    return root;
}