958. Check Completeness of a Binary Tree

958. Check Completeness of a Binary Tree

題意

題目要求檢查一個 binary 是否為 complete binary tree

• 除了最後一層外，每一層的節點數都應達到最大限度

• 且最後一層的 leaf 節點都集中於左側

限制

• The number of nodes in the tree is in the range [1, 100].

• 1 <= Node.val <= 1000

思考

• 為了判斷是否為 complete binary tree，需要確認

  • 所有的 leaf 應該在同一水平層

  • 任何非最後一層的節點不能有空缺

• 為了檢查這些條件，BFS是一個有效的策略

  • 將每個節點（包括空節點）依次放入一個 list 中

  • 檢查在遇到第一個空節點後是否還有非空節點存在

Implement 策略

1. 逐一遍歷列表中的每個節點，並將其左右子節點（不管是否為空）加入列表

   1. 變數 i 從0開始，代表 buf 中的索引

   2. 逐個處理 buf 中的節點，直到遇到第一個空節點

   3. 對於每個非空節點 buf[i]，將其左右子節點加入 buf

2. 當遇到第一個空節點後，確保列表中剩餘的所有節點都是空節點

   1. i 繼續增加，此時檢查 buf 中 i 之後的所有元素

   2. 如果 i 達到 buf.size()，意味著在列表中的空節點之後沒有任何非空節點，證明所有節點都已正確處理完畢

Solution

/**
 * 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();
    }
};