MediumRating 1628

117. Populating Next Right Pointers in Each Node II

linked-listtreedepth-first-searchbreadth-first-searchbinary-tree

解題說明

Populating Next Right Pointers in Each Node II

題目描述：給定一棵任意二元樹（非完全二元樹），其節點除了 val、left、right 之外還有一個 next 指標，初始值皆為 nullptr。請將每個節點的 next 指向同一層的下一個右邊節點；若右邊沒有節點，next 設為 nullptr。要求使用 O(1) 額外空間（不得使用佇列或陣列）。

解題思路：

本題是 LeetCode 116 的進階版——樹不再是完全二元樹，因此不能直接依賴 node->left->next = node->right 這類規律。核心技巧是：利用當前層已建立好的 next 指標，來建構下一層的 next 鏈。

逐層處理：維護 cur 指向當前層的最左節點；每次處理完當前層，就推進到下一層的最左節點。
虛擬頭節點（dummy head）技巧：在開始處理下一層之前，建立一個虛擬節點 dummy，並用 tail 指標追蹤下一層的「最後一個已串好的節點」。遍歷當前層時，每當遇到子節點，就把它接到 tail->next，並推進 tail。
利用 next 指標橫向移動：當前層的每個節點可透過 cur = cur->next 水平移動，這是 O(1) 空間實作的關鍵——不需要額外佇列，完全依賴已建立的 next 鏈。
推進至下一層：處理完當前層後，令 cur = dummy->next（即下一層的實際起點），進入下一輪迭代。

此做法時間複雜度 O(n)，空間複雜度 O(1)。

C++ 解法

複雜度分析

時間複雜度：O(n) — 每個節點恰好被走訪一次（外層迴圈逐層推進，內層迴圈處理當前層所有節點），n 為樹的節點總數。

空間複雜度：O(1) — 僅使用固定個數的指標變數（cur、dummy、tail），不使用佇列、堆疊或陣列；虛擬頭節點在堆疊上分配，不計入額外空間。

虛擬碼

1. If root is null, return null.
2. Set cur = root  (leftmost node of current level).
3. While cur is not null:
   a. Create a dummy node; set tail = dummy.
   b. While cur is not null:
      - If cur.left exists:  tail.next = cur.left;  tail = tail.next.
      - If cur.right exists: tail.next = cur.right; tail = tail.next.
      - Advance cur = cur.next  (move right on the current level).
   c. Advance cur = dummy.next  (move down to next level's first node).
4. Return root.

其他解法

方法一：BFS 佇列（Level-Order Traversal）

使用 queue<Node*> 進行標準 BFS，每次處理一整層時，將同層節點依序串接 next 指標。時間複雜度 O(n)，空間複雜度 O(n)（佇列最大存放一層所有節點，最壞情況為葉層的 n/2 個節點）。實作直觀，但不符合題目 O(1) 空間的要求。

方法二：DFS 遞迴（前序走訪）

以前序走訪（根→左→右）遞迴處理，利用已建立的 next 鏈橫向搜尋同層下一個可串接的子節點。空間複雜度 O(h)（h 為樹高，遞迴堆疊），最壞情況 O(n)。邏輯較複雜，且無法達到嚴格 O(1) 額外空間，但對完全二元樹（LeetCode 116）而言遞迴解較易理解。

延伸思考

本題相較於 LeetCode 116（完全二元樹版本），難點在哪裡？為什麼完全二元樹版可以使用更簡單的遞迴，而本題不行？
在迭代解法中，dummy 虛擬節點是在每一層的迴圈開始時建立的。如果改成在迴圈外只建立一次並反覆重置，有哪些細節需要注意（例如如何清除 dummy.next）？
若題目改為 N 叉樹（每個節點有最多 N 個子節點），如何修改本演算法以 O(1) 額外空間（不計遞迴堆疊）串接每層的 next 指標？