LeetCode [958] Check Completeness of a Binary Tree

Given a binary tree, determine if it is a complete binary tree.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example 1:

Input: [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Example 2:

Input: [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.

 

Note:

1. The tree will have between 1 and 100 nodes.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

/** * 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 { int maxLevel = -1; bool foundLast = false;//true if found a NULL at the last level public: bool isCompleteTree(TreeNode* root) { if(!root) return true; TreeNode* p = root; while(p){ maxLevel++; p = p->left; } return valid(root, 0); } bool valid(TreeNode* node, int level){ if(node==NULL){ if(level<maxLevel) return false; if(level==maxLevel) foundLast = true; return true; }else{ if(level>maxLevel) return false; if(level==maxLevel && foundLast) return false; return valid(node->left, level+1)&&valid(node->right, level+1); } } };