Description
給定一棵完美二元樹（perfect binary tree），將每個節點的
next指標指向其右邊的節點。如果右邊沒有節點，則next為null。
Example:
Input: root = [1,2,3,4,5,6,7] Output: [1,#,2,3,#,4,5,6,7,#]（# 代表 next 為 null 的層末端）
Intuition#
利用已建立的 next 指標做層序遍歷，不需要額外的佇列空間。
- BFS 層序遍歷是直觀解法
- 但利用完美二元樹的性質和已建立的
next指標，可以達到O(1)空間
Approaches#
1: BFS（Queue）#
- 概念: 標準 BFS 層序遍歷，同一層的節點依序連接 next 指標
- 時間複雜度:
O(n) - 空間複雜度:
O(n)（佇列）
BFS 程式碼
class Solution {
fun connect(root: Node?): Node? {
if (root == null) return null
val queue: ArrayDeque<Node> = ArrayDeque()
queue.add(root)
while (queue.isNotEmpty()) {
val size = queue.size
for (i in 0 until size) {
val node = queue.removeFirst()
if (i < size - 1) {
node.next = queue.first()
}
node.left?.let { queue.add(it) }
node.right?.let { queue.add(it) }
}
}
return root
}
}⭐2: 利用 Next 指標的層序遍歷#
- 概念: 用當前層已建立的 next 指標遍歷，為下一層建立 next 連接
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun connect(root: Node?): Node? {
var leftmost = root
while (leftmost?.left != null) {
var current = leftmost
while (current != null) {
// 連接同一父節點的左右子節點
current.left!!.next = current.right
// 連接不同父節點的子節點
if (current.next != null) {
current.right!!.next = current.next!!.left
}
current = current.next
}
leftmost = leftmost.left
}
return root
}
}完美二元樹保證每個非葉節點都有左右子節點。外層迴圈走最左邊節點（往下一層），內層迴圈透過
next橫向遍歷同一層。
🔑 Takeaways#
- Pattern: 利用已建立的結構進行遍歷
- 關鍵技巧: 兩種連接：(1) 同父的
left.next = right，(2) 跨父的right.next = parent.next.left。這個技巧利用了上一層已建好的 next 指標來遍歷