判斷完全二叉樹演算法：層序遍歷 + 旗標法 Java 實作

前言

完全二叉樹是堆、優先隊列等資料結構的基礎。判斷一棵二叉樹是否為完全二叉樹，核心在於：**層序遍歷過程中，一旦出現「缺失右子節點」或「缺失左子節點但有右子節點」的情況，後續所有節點必須為葉子節點**。本文提供標準隊列 BFS 實作與邊界情況分析。

完全二叉樹定義回顧

• 除最後一層外，每層節點數達最大值 (2^h)。
• 最後一層節點**集中在最左側**，中間無空隙。
• 滿二叉樹是完全二叉樹的特例。

演算法邏輯

1. 隊列初始化放入根節點。
2. 布林旗標 leafPhase = false 表示「是否已進入必須為葉子節點階段」。
3. 迴圈出隊節點 cur，檢查左右子節點：
   a. 若 leafPhase == true 且 cur 有任一子節點 → **非完全**。
   b. 若 cur.left == null && cur.right != null → **非完全** (缺左有右)。
   c. 若 cur.right == null → 設 leafPhase = true (後續必須全葉子)。
4. 非空子節點入隊。
5. 遍歷結束無違規 → **完全二叉樹**。

Java 完整實作

複雜度分析

    
時間複雜度：O(N) — 每個節點入隊出隊各一次。
    
空間複雜度：O(W) — 隊列最大寬度，最差 O(N) (滿二叉樹最後一層)。


常見變體與延伸

    
問題
解法調整
    
判斷滿二叉樹
遍歷中任一節點 left == null ^ right == null (異或) 即非滿；或計算節點數 == 2h+1-1。
    
計算完全二叉樹節點數 (LeetCode 222)
利用完全性質：左右子樹高度相等 → 左滿 (2h-1) + 1 + 遞歸右；否則右滿 + 遞歸左。O(log2N)。
    
驗證堆屬性 (最大/最小堆)
在 BFS 中額外檢查 parent.val >= left.val && parent.val >= right.val。
    
從數組索引判斷 (隱式完全二叉樹)
數組索引 i，左子 2i+1，右子 2i+2。若所有非葉節點索引 < n/2 且子索引 < n，則為完全。


總結
層序遍歷 + leafPhase 旗標是判斷完全二叉樹最直觀、最穩健的演算法。關鍵在於識別「第一個缺失右子節點的節點」作為分水嶺，其後所有節點必須為葉子。此邏輯同樣適用於堆建立驗證、完全二叉樹節點數統計等衍生問題。