// 演算法 / Algorithm:
// 與 C 版完全相同：逐層處理。目前層的 next 鏈當作「走訪用的串列」，
// 用一個 dummy 節點加上 tail 指標，把下一層的孩子依序串接起來。
// 只用固定幾個指標 → O(1) 額外空間。
// Same as the C version: level by level. Treat the current level's next-chain as the
// traversal list; use a dummy node plus a tail pointer to thread the next level's children.
// A fixed number of pointers → O(1) extra space.

class Solution {
public:
    Node* connect(Node* root) {
        // cur：目前正在處理的那一層的最左節點 / leftmost node of the level being processed
        Node* cur = root;

        // 外層迴圈：一層一層往下，直到沒有節點 / outer loop: descend level by level until empty
        while (cur != nullptr) {

            // dummy 是虛擬頭節點；dummy.next 最終指向下一層的第一個節點
            // dummy is a placeholder head; dummy.next ends up pointing to the next level's first node
            Node dummy(0);            // 用值 0 建構一個臨時節點 / construct a temporary node with value 0

            // tail 指向「下一層鏈的目前尾端」，初始為 &dummy
            // tail points to the tail of the next level's chain, initially &dummy
            Node* tail = &dummy;

            // range 走法：沿目前層的 next 鏈逐一走訪 node
            // Walk the current level via its next chain, node by node
            for (Node* node = cur; node != nullptr; node = node->next) {

                // 左孩子存在就接上並前進 tail / if left child exists, append and advance tail
                if (node->left) {
                    tail->next = node->left;
                    tail = tail->next;    // tail 前進到剛接上的節點 / move tail to the node just linked
                }
                // 右孩子存在就接上並前進 tail / if right child exists, append and advance tail
                if (node->right) {
                    tail->next = node->right;
                    tail = tail->next;
                }
            }

            // 這一層處理完。tail->next 明確設 nullptr 作為下一層結尾
            // Level done; explicitly terminate the next level's chain
            tail->next = nullptr;

            // 前往下一層的第一個節點 / advance to the next level's first node
            cur = dummy.next;
        }

        // 回傳原根節點，樹已就地連接完成 / return root; the tree is linked in place
        return root;
    }
};