958. Check Completeness of a Binary Tree

題目連結: 958. Check Completeness of a Binary Tree

題目描述

給定一個二元樹，請判斷它是否是一個完全二元樹。

• 完全二元樹的定義是：除了最後一層之外，每一層的節點都達到最大數量，且最後一層的節點都盡可能地靠左排列。

限制條件

• 樹中節點的數量範圍為 [1, 100]。
• 1 <= Node.val <= 1000

解題思路

為了判斷一個二元樹是否為完全二元樹，我們需要確認以下兩點：

1. 除了最後一層之外，所有層級的節點數都達到最大值。
2. 最後一層的節點必須從左到右連續排列，中間不能有空缺。

使用廣度優先搜尋（BFS）是解決此問題的有效方法。我們可以逐層遍歷二元樹，並在遇到第一個空節點後，檢查之後是否還存在非空節點。如果在遇到空節點後仍有非空節點，則該樹不是完全二元樹。

詳細解釋

• 為何需要在遇到第一個空節點後，檢查之後的節點是否全部為空：
  • 在完全二元樹中，空節點只能出現在最後一層或倒數第二層的右側。
  • 如果在遇到第一個空節點後，仍然存在非空節點，表示樹中存在節點空缺，不符合完全二元樹的定義。
• 示例：
  • 假設有以下二元樹：

    1
   / \
  2   3
 / \   \
4   5   7

• 這棵樹不是完全二元樹，因為在第二層的右子節點缺少左子節點。
• 使用上述方法，buf 會在遇到空節點後（3 的左子節點），仍然發現非空節點（7），因此判斷為非完全二元樹。

具體步驟

1. 初始化一個隊列或陣列 buf，將根節點 root 放入其中。
2. 使用索引 i 進行遍歷：
   • 第一階段：
     • 當 i 小於 buf 的大小，且 buf[i] 不為空時：
       • 將 buf[i] 的左子節點 buf[i]->left 和右子節點 buf[i]->right（不論是否為空）加入 buf。
       • i 增加 1。
   • 第二階段：
     • 當 i 小於 buf 的大小，且 buf[i] 為空時：
       • i 增加 1。
3. 判斷結果：
   • 如果在遇到第一個空節點後，buf 中仍存在非空節點，則 i 不等於 buf.size()，表示樹中存在空缺，不是完全二元樹。
   • 否則，i 等於 buf.size()，表示樹是完全二元樹。

程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        vector<TreeNode*> buf;
        buf.push_back(root);
        int i = 0;
        while (i < buf.size() && buf[i]) {
            buf.push_back(buf[i]->left);
            buf.push_back(buf[i]->right);
            i += 1;
        }

        while (i < buf.size() && !buf[i]) {
            i += 1;
        }
        return i == buf.size();
    }
};

時間與空間複雜度分析

時間複雜度：O(n)

• 解釋：
  • n 為二元樹中的節點總數。
  • 我們需要遍歷每個節點一次，將其子節點加入 buf，所以時間複雜度為 O(n)。

空間複雜度：O(n)

• 解釋：
  • 我們使用了一個陣列 buf 來存儲所有的節點（包括空節點）。
• 詳細計算：
  • 在最壞情況下，二元樹為滿二元樹，節點數為 n，葉節點數約為 n/2。
  • 陣列 buf 需要存儲所有節點及其子節點（包括空節點），所以空間複雜度為 O(n)。