958. 二叉樹的完全性檢驗

思路

一個完全二叉樹，除了最後一列外，每一列的節點都要是滿的，最後一列如果不是滿的，則最後一列的節點應該要盡量靠左。判斷依據如下\

程式碼

1

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        const int MX = 1001;
        bool leaf = false;
        TreeNode* q[MX];
        int left = 0, right = 0;
        q[right++] = root;
        TreeNode* cur;
        while(left < right) {
            cur = q[left++];
            if(!cur->left && cur->right || (leaf && (cur->left || cur->right))) return false; // 有右無左 || 應該要是葉節點, 卻不是
            
            if(cur->left) q[right++] = cur->left;
            if(cur->right) q[right++] = cur->right;
            
            if(!cur->left || !cur->right) { // 有缺, 接下來的點都要是葉節點
                leaf = true;
            }
        }
        return true;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$