MediumRating 1703
958. Check Completeness of a Binary Tree
treebreadth-first-searchbinary-tree
解題說明
Check Completeness of a Binary Tree
題目描述：
給定一棵二元樹的根節點 root，判斷它是否為完全二元樹（Complete Binary Tree）。完全二元樹的定義：除了最後一層外，每一層都被完全填滿，且最後一層的節點盡量靠左排列。
解題思路： BFS 層序遍歷：
在完全二元樹的層序遍歷中，一旦遇到 null 節點，後面不應該再出現任何非 null 節點。
- 使用 BFS 遍歷樹（允許將
null加入佇列）。 - 設一個旗標
seenNull，當第一次遇到null時設為true。 - 之後若再遇到非
null的節點，則不是完全二元樹。
C++ 解法
複雜度分析
時間複雜度：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) 空間。遞迴計算每個子樹的高度和節點數，驗證完全二元樹的結構性質。邏輯較複雜但棧空間更小。
延伸思考
- 「遇到 null 後不應再有非 null 節點」這個性質為什麼等價於完全二元樹的定義？
- 節點編號法（根 = 1，左 = 2i，右 = 2i+1）與完全二元樹的陣列表示有何關聯？
- 如何判斷一棵樹是否為「滿二元樹」（Full Binary Tree）？與完全二元樹的判斷有何差異？