Count Complete Tree Nodes
Given a complete binary tree, count the number of nodes.
Constraints:
- The tree is a complete binary tree.
- The number of nodes in the tree is in the range [1, 10^4].
- The values of the nodes are in the range [1, 10^4].
Examples:
Input: [1,2,3,4,5,6]
Output: 6
Explanation: The tree is a complete binary tree with 6 nodes.
Solutions
Level Order Traversal
Time: O(n)Space: O(n)
This solution uses a level order traversal to count the number of nodes in the tree. It starts by checking if the root is null, and if so, returns 0. Then it initializes a queue with the root node and a count variable to 0. It enters a loop that continues until the queue is empty. In each iteration, it dequeues a node, increments the count, and enqueues the node's left and right children if they exist. Finally, it returns the count.
int countNodes(TreeNode* root) {
if (!root) return 0;
queue<TreeNode*> q;
q.push(root);
int count = 0;
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
count++;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
return count;
}Follow-up:
How would you modify the solution to count the number of nodes in a binary tree that is not complete?
