給定一棵二元樹的根節點，判斷它是否為完全二元樹。完全二元樹除了最後一層外，每層都完全填滿，且最後一層的節點盡量靠左。
Example:
Input: root = [1,2,3,4,5,6] Output: true
Intuition
TIP
BFS 遍歷時，遇到 null 後不應該再出現非 null 節點。
- 完全二元樹的特性：在層序遍歷中，所有非 null 節點必須連續出現
- 一旦遇到第一個 null，之後所有節點都必須是 null
- 用 BFS 逐層掃描，設定一個旗標記錄是否已遇到 null
Approaches
1. BFS + Flag — O(n) / O(n)
- Idea: 層序遍歷，遇到 null 設旗標，之後若再遇到非 null 節點就不是完全二元樹
- Time:
O(n) - Space:
O(n)
class Solution {
fun isCompleteTree(root: TreeNode?): Boolean {
if (root == null) return true
val queue: Queue<TreeNode?> = LinkedList()
queue.offer(root)
var seenNull = false
while (queue.isNotEmpty()) {
val node = queue.poll()
if (node == null) {
seenNull = true
} else {
if (seenNull) return false
queue.offer(node.left)
queue.offer(node.right)
}
}
return true
}
}⭐ 2. BFS + Index Check — O(n) / O(n)
- Idea: 為每個節點編號（根為 1，左子 2i，右子 2i+1），若樹是完全的，最大編號應等於節點總數
- Time:
O(n) - Space:
O(n)
class Solution {
fun isCompleteTree(root: TreeNode?): Boolean {
if (root == null) return true
val queue: Queue<Pair<TreeNode, Int>> = LinkedList()
queue.offer(root to 1)
var count = 0
var maxIndex = 0
while (queue.isNotEmpty()) {
val (node, index) = queue.poll()
count++
maxIndex = maxOf(maxIndex, index)
node.left?.let { queue.offer(it to index * 2) }
node.right?.let { queue.offer(it to index * 2 + 1) }
}
return maxIndex == count
}
}🔑 Takeaways
- Pattern: 完全二元樹的判定可以透過 BFS 層序遍歷檢查 null 的連續性
- Key trick: 「遇到 null 後不能再有非 null」是最直覺的判定方式；索引法則提供了另一種數學角度的驗證