500. Count Complete Tree
A theatre lays its seats out as a complete binary tree rooted at root: every row is full except possibly the last one, and the seats in the last row sit as far to the left as possible. Counting seats one by one is too slow for very large halls.
Return the total number of nodes in the tree rooted at root. The input is guaranteed to be a complete binary tree, and an empty tree has 0 nodes. Your method should do noticeably better than visiting every node by exploiting the complete shape.
Example 1
- Input:
- root = [4,7,1,9,3,8]
- Output:
- 6
- Explanation:
The tree has three levels with the last one holding 3 of its 4 slots, giving 1 + 2 + 3 = 6 nodes.
Example 2
- Input:
- root = [2,9,4,1,6,3,8,5,7,2]
- Output:
- 10
- Explanation:
Levels hold 1, 2, 4 and 3 nodes, so there are 10 nodes.
Constraints
0 ≤ number of nodes in root ≤ 106
0 ≤ Node.val ≤ 1000
root is guaranteed to be a complete binary tree.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 240 msC++ 60 msJava 120 msJavaScript 120 msTypeScript 120 ms
Expected complexity
- Time
- O(log^2 n)
- Space
- O(log n)