Count the Nodes of a Complete Tree Without Visiting Them All
Implement countNodes
You are given the root of a complete binary tree: every level except possibly the last is completely filled, and the last level's nodes are packed as far left as possible. Return the number of nodes in the tree.
Counting the nodes one by one takes O(n) time. Because the tree is complete, you can do better: a subtree whose left edge and right edge have the same number of nodes is completely full, and its size follows directly from its height.
Example 1:
Input: root = [3,8,5,2,9,7,4,6,1,10]
Output: 10
Example 2:
Input: root = [6,2,9]
Output: 3
Example 3:
Input: root = []
Output: 0
+ 13 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes ≤ 5000; 1 ≤ node.val ≤ 90 (the values themselves never affect the answer) - ●
The tree is complete: every level except possibly the last is completely filled, and the nodes of the last level sit as far to the left as possible - ●
Return how many nodes the tree has - ●
A solution faster than O(n) is expected: it should take fewer than n steps by using the complete-tree shape
root =
[3, 8, 5, 2, 9, 7, 4, 6, 1, 10]