Complete Binary Tree

题目：

Check a binary tree is completed or not. A complete binary tree is a binary tree that every level is completed filled except the deepest level. In the deepest level, all nodes must be as left as possible. See more definition

分析：

这题目经典之处在于，用levelorder的方法把tree中所有的结点收集起来，具体方法很灵巧，如下：

for (int i = 0; i < Q.size(); i++) {
    TreeNode* temp = Q[i];
    if (temp != NULL) {
        Q.push_back(temp->left);
        Q.push_back(temp->right);
    }
}

注意这方法导致这道题目还真的不能用queue解决，因为queue不支持random element access，但是deque是可以的哈哈哈哈。

解法：

class Solution {
public:
    /**
     * @param root, the root of binary tree.
     * @return true if it is a complete binary tree, or false.
     */
    bool isComplete(TreeNode* root) {
        // Write your code here
        if (root == NULL) {
            return true;
        }
        vector<TreeNode*> Q;
        Q.push_back(root);

        for (int i = 0; i < Q.size(); i++) {
            TreeNode* temp = Q[i];
            if (temp != NULL) {
                Q.push_back(temp->left);
                Q.push_back(temp->right);
            }
        }

        bool existNull = false;
        for (int i = 0; i < Q.size(); i++) {
            if (Q[i] == NULL && existNull == false) {
                existNull = true;
                continue;
            }
            if (existNull == true && Q[i] != NULL) {
                return false;
            }
        }

        return true;
    }
};