117. Populating Next Right Pointers in Each Node II

題目 / Problem

中文： 給定一棵二元樹，每個節點結構如下：

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

請把每個節點的 next 指標指向「同一層、緊接在它右邊」的節點。如果右邊沒有節點，next 就設為 NULL。一開始所有 next 都是 NULL。注意：這棵樹不一定是完美二元樹（節點可以缺左或缺右孩子），這是本題比 116 題難的地方。

English: Given a binary tree where each node has a next pointer, connect each node's next to the node immediately to its right on the same level. If there's no node to its right, set next to NULL. Initially all next pointers are NULL. Unlike problem 116, this tree is not necessarily perfect — nodes may be missing a left or right child — which is what makes it harder.

Constraints / 限制: - 節點數量在 [0, 6000] 之間 / Number of nodes is in [0, 6000]. - -100 <= Node.val <= 100.

Example / 範例:

Input:  root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]

樹的形狀 / The tree looks like:

        1
       / \
      2   3
     / \   \
    4   5   7

連接後每一層 / After linking, each level: - Level 0: 1 -> NULL - Level 1: 2 -> 3 -> NULL - Level 2: 4 -> 5 -> 7 -> NULL（注意 5 直接連到 7，跳過了 3 缺失的左孩子 / note 5 connects straight to 7, skipping node 3's missing left child）

名詞解釋 / Glossary

• 二元樹 / Binary tree：每個節點最多有兩個孩子（左孩子 left、右孩子 right）的樹狀結構。/ A tree where each node has at most two children, left and right.
• 層 / Level：離根節點距離相同的所有節點組成一層。根是第 0 層，它的孩子是第 1 層，依此類推。/ All nodes at the same distance from the root form one level; the root is level 0, its children level 1, and so on.
• 指標 / Pointer：一個變數，裡面存的是「另一個節點的記憶體位址」，用 -> 來存取它指向的節點的成員。/ A variable holding the memory address of another node; use -> to reach members of the node it points to.
• BFS / 廣度優先搜尋 (Breadth-First Search)：一層一層地走訪樹，通常用佇列 (queue) 實作。適合本題，但需要額外空間。/ Visiting the tree level by level, usually with a queue. Natural for this problem but needs extra space.
• 佇列 / Queue：先進先出 (FIFO) 的容器，BFS 用它暫存「待處理的節點」。/ A first-in-first-out container used by BFS to hold nodes waiting to be processed.
• 虛擬頭節點 / Dummy node：一個臨時的、不屬於真正資料的節點，放在一條鏈結串列的最前面，讓我們「不用特別處理第一個節點」的邊界情況。/ A throwaway placeholder node placed before a linked list so we don't need special-case logic for the first real node.
• 常數額外空間 / Constant extra space O(1)：不論輸入多大，額外使用的記憶體都是固定幾個變數，不隨節點數成長。/ Extra memory stays a fixed handful of variables regardless of input size.
• 原地 / In-place：直接利用已有的結構（這裡是每一層已建好的 next 鏈）來走訪，不另外配置容器。/ Reusing the existing structure (here, the next chain of the level just built) to traverse, without allocating a separate container.

思路

中文： 最直覺的做法是 BFS：用一個佇列，一層一層地把節點拿出來，把同一層相鄰的節點用 next 串起來。這是對的，也很好懂，但它需要一個佇列，最壞情況下佇列裡會塞滿一整層的節點，也就是 O(n) 的額外空間。題目的 follow-up 要求「只用常數額外空間」，所以我們要想更聰明的辦法。

關鍵觀察是：當我們正在處理第 k 層時，第 k 層的 next 指標其實已經被上一輪串好了。 也就是說，第 k 層本身就是一條用 next 連起來的鏈結串列！我們可以沿著這條現成的鏈，從左走到右，順便去「連接」它們的孩子（也就是第 k+1 層）。這樣就不需要佇列了——上一層的 next 鏈就是我們的「佇列」。

問題只剩下：走在第 k 層時，怎麼把第 k+1 層一個個孩子接起來？因為樹不完美，孩子可能缺左或缺右，直接判斷「誰的右邊是誰」會很囉唆。技巧是用一個虛擬頭節點 dummy：我們維護一個 tail 指標，一開始指向 dummy。每當在第 k 層遇到一個孩子（先左後右，只要它存在），就把它接到 tail->next，然後 tail 前進到這個孩子。這樣不管孩子怎麼缺，我們永遠只是「把下一個存在的孩子接到目前這條鏈的尾巴」，邏輯統一、不用分很多情況。走完第 k 層後，dummy->next 就是第 k+1 層的第一個節點，我們跳過去繼續處理下一層，直到沒有下一層為止。

English: The most natural approach is BFS: use a queue, pop the tree level by level, and link neighbors on each level via next. That's correct and easy to grasp, but it needs a queue that in the worst case holds an entire level — O(n) extra space. The follow-up asks for constant extra space, so we need something smarter.

The key insight: by the time we process level k, level k's next pointers are already wired up from the previous round. In other words, level k is itself a linked list threaded by next. We can walk that ready-made list left to right and, as we go, connect the children (level k+1). No queue needed — the previous level's next chain is our queue.

The only remaining question is how to link level k+1's children while walking level k. Because the tree is imperfect, children may be missing on either side, and reasoning about "whose right neighbor is whom" gets messy. The trick is a dummy head node: keep a tail pointer starting at dummy. Whenever we meet a child on level k (left then right, if it exists), we attach it to tail->next and advance tail to it. No matter which children are missing, we're always just "append the next existing child to the tail of the chain we're building" — one uniform rule, no case explosion. After finishing level k, dummy->next is the first node of level k+1; we jump there and repeat until there's no next level.

逐步走查 / Walkthrough

以 root = [1,2,3,4,5,null,7] 為例 / Using the tree:

        1
       / \
      2   3
     / \   \
    4   5   7

外層迴圈：cur 從每層的最左節點開始，沿 next 走。內層每次處理一層，用 dummy + tail 建下一層的鏈。 Outer loop: cur starts at the leftmost node of a level and walks via next; each pass builds the next level's chain using dummy + tail.

Level 0（處理第 0 層，連接第 1 層）/ Processing level 0, building level 1:

結果 / Result: dummy->next = 2，第 1 層變成 2 -> 3 -> NULL。下一輪 cur = 2。

Level 1（處理第 1 層，連接第 2 層）/ Processing level 1, building level 2:

結果 / Result: dummy->next = 4，第 2 層變成 4 -> 5 -> 7 -> NULL。注意 5 直接接到 7，因為我們是「找下一個存在的孩子」，自動跳過了 3 缺失的左孩子。下一輪 cur = 4。

Level 2（處理第 2 層）/ Processing level 2: 4、5、7 都沒有孩子，走完整層後 dummy->next 仍是 NULL，所以 cur 變成 NULL，外層迴圈結束。/ None of 4, 5, 7 has children; after the pass dummy->next is still NULL, so cur becomes NULL and the outer loop ends.

Solution — C

// 演算法 / 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;
}

Solution — C++

// 演算法 / 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;
    }
};

複雜度 / Complexity

• Time: O(n) — 每個節點恰好被造訪常數次：一次是走它所在層的 next 鏈（讀取它、看它的孩子），孩子被接上時也是常數操作。n 是節點總數，所以總時間與節點數成正比。/ Each node is visited a constant number of times (once when we walk its level, plus constant work when it's appended as a child). n is the total number of nodes, so total time is linear.
• Space: O(1) — 除了輸入的樹以外，只用了 cur、dummy、tail、node 幾個指標，數量固定、不隨 n 成長。我們沒有用佇列，而是重複利用上一層已建好的 next 鏈。/ Aside from the input tree we use only a fixed handful of pointers; no queue. We reuse the already-built next chain of the previous level, so extra space is constant.

Pitfalls & Edge Cases

• 空樹 / Empty tree (root == NULL)：while (cur != NULL) 一開始就為假，直接回傳 NULL，不會誤存取空指標。/ The while condition is immediately false, so we return NULL safely without dereferencing a null pointer.
• 忘記結尾設 NULL / Forgetting to terminate each level：dummy 沒初始化時 next 是垃圾值；每層結束一定要 tail->next = NULL，否則最右節點會指向前一輪的殘留位址，造成錯誤甚至無限迴圈。程式碼在每層結束時明確清 NULL。/ dummy.next starts as garbage; you must set tail->next = NULL after each level, or the rightmost node keeps a stale pointer, risking wrong output or an infinite loop. The code clears it explicitly.
• 不完美樹的缺孩子 / Missing children in an imperfect tree：這是本題核心陷阱。不能假設「node 的右孩子的下一個是下一個 node 的左孩子」。用 dummy+tail「只接存在的孩子」的寫法，自動跳過缺失的孩子（例如範例中 5 直接接到 7）。/ The core trap: you cannot assume neighbor relationships between children. The dummy+tail "append only existing children" pattern skips gaps automatically (e.g. 5 links straight to 7).
• 必須先左後右 / Order matters: left before right：同一父節點下，左孩子在右孩子左邊，所以迴圈內一定先檢查 left 再 right，順序反了會把同層順序弄亂。/ Under one parent the left child sits left of the right child, so check left before right; swapping them corrupts the level ordering.
• 不要用值當條件判斷 / Don't test node values：節點值範圍含負數與 0（-100..100），判斷是否存在只能用指標是否為 NULL，不能用 if (node->left->val) 之類，否則值為 0 的節點會被誤判。程式一律用指標判斷。/ Values include 0 and negatives, so test existence with the pointer (!= NULL), never the value — a node with value 0 would be wrongly skipped otherwise.