958. Check Completeness of a Binary Tree

Medium
Description

給定一棵二元樹的根節點，判斷它是否為完全二元樹。完全二元樹除了最後一層外，每層都完全填滿，且最後一層的節點盡量靠左。

Example:

Input: root = [1,2,3,4,5,6] Output: true

Intuition#

BFS 遍歷時，遇到 null 後不應該再出現非 null 節點。

  • 完全二元樹的特性：在層序遍歷中，所有非 null 節點必須連續出現
  • 一旦遇到第一個 null，之後所有節點都必須是 null
  • 用 BFS 逐層掃描，設定一個旗標記錄是否已遇到 null

Approaches#

1: BFS + 旗標#

  • 概念: 層序遍歷，遇到 null 設旗標，之後若再遇到非 null 節點就不是完全二元樹
  • 時間複雜度: O(n)
  • 空間複雜度: 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 + 索引檢查#

  • 概念: 為每個節點編號（根為 1，左子 2i，右子 2i+1），若樹是完全的，最大編號應等於節點總數
  • 時間複雜度: O(n)
  • 空間複雜度: 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 的連續性
  • 關鍵技巧: 「遇到 null 後不能再有非 null」是最直覺的判定方式；索引法則提供了另一種數學角度的驗證