題目描述:
給定一棵完美二元樹(Perfect Binary Tree),將每個節點的 next 指標指向同一層的右側節點。若無右側節點則指向 NULL。
解題思路:
利用完美二元樹的性質與已建立的 next 指標,可以用 O(1) 額外空間解決。逐層處理:
leftmost 指標追蹤每層最左邊的節點。curr 遍歷該層所有節點(透過 next 指標橫向移動)。curr 節點:
curr->left->next = curr->rightcurr->next 存在,則 curr->right->next = curr->next->leftleftmost 下移到下一層的最左節點。這利用了上一層已建好的 next 鏈來處理下一層,不需要佇列。
時間複雜度: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 rootBFS 層序遍歷:使用佇列進行標準 BFS,在每層中將前一個節點的 next 指向當前節點。時間 O(n),空間 O(n)(佇列最多存放最後一層 n/2 個節點)。實作直觀但不滿足 O(1) 空間的進階要求。
遞迴 DFS:對每個節點遞迴連接其子節點與跨父節點的連接。時間 O(n),空間 O(log n) 遞迴深度。程式碼簡潔但隱含的遞迴堆疊空間不滿足嚴格的 O(1) 要求。
next 指標當作佇列,還有哪些問題可以用類似的「已建立的結構代替額外資料結構」的技巧?