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:
- The tree will have between 1 and 100 nodes.
Solution:
Level order traversal, if any nodes appears after a missing node then the tree is not a perfect binary tree.
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { public: bool isCompleteTree(TreeNode* root) { if (!root) return true; queue<TreeNode> q; q.push(root); bool missing = false; while (!q.empty()) { auto size = q.size(); while (size--) { auto node = q.front(); q.pop(); if (node) { if (missing) return false; q.push(node->left); q.push(node->right); } else { missing = true; } } } return true; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution: def isCompleteTree(self, root): if not root: return True q = collections.deque([root]) missing = False while q: size = len(q) while size > 0: size -= 1 node = q.popleft() if node: if missing: return False q.append(node.left) q.append(node.right) else: missing = True return True |
