Leetcode 998 Solution

This article provides solution to leetcode question 998 (check-completeness-of-a-binary-tree)
Categories:
Tags:
Access this page by simply typing in "lcs 998" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/check-completeness-of-a-binary-tree

Solution

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        queue<TreeNode*> q;

        int level_size = 1;
        q.push(root);

        while (!q.empty())
        {
            int s = q.size();
            int state = 0;

            for (int i = 0; i < s; i++)
            {
                auto node = q.front();
                q.pop();

                if (node->left)
                {
                    if (state == 1)
                        return false;
                    q.push(node->left);
                }
                else
                    state = 1;

                if (node->right)
                {
                    if (state == 1)
                        return false;
                    q.push(node->right);
                }
                else
                    state = 1;
            }

            if (s != level_size && q.empty() == false)
                return false;

            level_size *= 2;
        }

        return true;
    }
};