Medium
116. Populating Next Right Pointers in Each Node
linked-listtreedepth-first-searchbreadth-first-searchbinary-tree
解題說明
Populating Next Right Pointers in Each Node
題目描述：
給定一棵完美二元樹（Perfect Binary Tree），將每個節點的 next 指標指向同一層的右側節點。若無右側節點則指向 NULL。
解題思路：
利用完美二元樹的性質與已建立的 next 指標，可以用 O(1) 額外空間解決。逐層處理：
- 從根節點開始，用
leftmost指標追蹤每層最左邊的節點。 - 在當前層，用
curr遍歷該層所有節點（透過next指標橫向移動）。 - 對每個
curr節點：- 左子連右子：
curr->left->next = curr->right - 右子連下一組的左子：若
curr->next存在，則curr->right->next = curr->next->left
- 左子連右子：
- 處理完一層後，
leftmost下移到下一層的最左節點。
這利用了上一層已建好的 next 鏈來處理下一層，不需要佇列。
C++ 解法
複雜度分析
時間複雜度：O(n) — 每個節點恰好被訪問一次。
空間複雜度：O(1) — 只使用 leftmost 和 curr 兩個指標，不需要額外佇列或遞迴堆疊。
虛擬碼
1. If root is null, return null
2. Set leftmost = root
3. While leftmost has a left child:
a. Set curr = leftmost
b. While curr is not null:
- curr.left.next = curr.right
- If curr.next exists: curr.right.next = curr.next.left
- curr = curr.next
c. leftmost = leftmost.left
4. Return root其他解法
BFS 層序遍歷：使用佇列進行標準 BFS，在每層中將前一個節點的 next 指向當前節點。時間 O(n)，空間 O(n)（佇列最多存放最後一層 n/2 個節點）。實作直觀但不滿足 O(1) 空間的進階要求。
遞迴 DFS：對每個節點遞迴連接其子節點與跨父節點的連接。時間 O(n)，空間 O(log n) 遞迴深度。程式碼簡潔但隱含的遞迴堆疊空間不滿足嚴格的 O(1) 要求。
延伸思考
- 若不是完美二元樹而是任意二元樹，此方法需要如何修改？（LeetCode 117）
- 此 O(1) 空間的技巧本質上是利用已建好的
next指標當作佇列，還有哪些問題可以用類似的「已建立的結構代替額外資料結構」的技巧？ - 若樹的深度很大，遞迴 DFS 可能導致堆疊溢位，迭代的 O(1) 空間解法有什麼實際優勢？