題目描述:
給定一棵二元樹的根節點 root,判斷它是否為完全二元樹(Complete Binary Tree)。完全二元樹的定義:除了最後一層外,每一層都被完全填滿,且最後一層的節點盡量靠左排列。
解題思路: BFS 層序遍歷:
在完全二元樹的層序遍歷中,一旦遇到 null 節點,後面不應該再出現任何非 null 節點。
null 加入佇列)。seenNull,當第一次遇到 null 時設為 true。null 的節點,則不是完全二元樹。時間複雜度:O(n) — 每個節點恰好被訪問一次。
空間複雜度:O(n) — BFS 佇列在最差情況下存放最後一層的所有節點,約 n/2 個。
1. If root is null, return true.
2. Initialize queue with root; set seenNull = false.
3. While queue is not empty:
a. Dequeue node.
b. If node is null: set seenNull = true.
c. Else:
- If seenNull is true: return false.
- Enqueue node.left and node.right (including nulls).
4. Return true.節點編號法:O(n) 時間、O(n) 空間。用 BFS 給每個節點編號(根 = 1,左子 = 2i,右子 = 2i+1)。若最大編號等於節點總數,則為完全二元樹。
DFS + 高度檢查:O(n) 時間、O(h) 空間。遞迴計算每個子樹的高度和節點數,驗證完全二元樹的結構性質。邏輯較複雜但棧空間更小。