Problems - Complete Tree Problems
Note the definition of Complete Tree and Perfect Tree
| Problems |
Solutions |
Key Points |
code |
Complexity |
| 222. Count Complete Tree Nodes |
Sub task. Combine the normal tree and perfect tree |
How to calculate the time complexity |
code |
O(lgN*logN) |
|
|
|
|
- |
Time Complexity Analyze
Let's consider a complete tree with N nodes.
Since ONE sub tree of a complete tree must be a perferect tree, so we have
T(N)=O(lgN)+T(N/2)
For the perfect sub tree, we have O(lgN), and the other sub tree, there is T(N/2). And similarly, we have
T(N/2)=O(lg(N/2))+T(N/4)
T(N/4)=O(lg(N/4))+T(N/8)
So, we actually have
T(N)=O(lgN)+T(N/2)
=O(lgN)+O(lg(N/2))+T(N/4)
=O(lgN)+O(lg(N/2))+O(lg(N/4))+T(N/8)
=O(lg(N/20))+O(lg(N/21))+O(lg(N/22))+......+O(lg(N/2i))
=O(lgN−0)+O(lgN−1)+O(lgN−2)+......+O(lgN−i)
As we know, the max value of i is lgN, so we have
T(N)=O(lgN)+O(lgN)−O(1)+O(lgN)−O(lgN)−O(2)+......O(lgN)−O(lgN)
=O((0+lgN)(lgN+1)/2)
=O(lgN∗lgN)