**Count Complete Tree Nodes**

#### Description

Given a complete binary tree, count the number of nodes.

The definition of a complete binary tree:

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.

满二叉树(Full binary tree): 所有的非叶子节点都要有两个孩子, 可以只有右孩子.

完全二叉树(Complete binary tree)： 最后一层的叶子节点在左侧, 也就是不能只有右孩子而没有左孩子.

完美二叉树(Perfect binary tree): 完美的三角形。 (2 ^ h - 1 nodes in total)

#### Example

1 | Input: |

#### Solution

##### O(N) Solution

The first thought is to visit each node in this tree and count the total number. And it can be explained by the following code.

*Python*

1 | def countNodes(root): |

This is pretty easy, right? BUT, the time complexity of this algorithm is O(N), because we visit every node of this tree.

##### O(lgn ^ 2) Solution

WE CAN DO BETTER!!! (my algorithm teacher likes this sentence pretty much.)

Since this is a complete tree, what is special of a complete tree, as we talked above, if this is a perfect binary tree, then we can use the formular (2 ^ h - 1) to calculate the total nodes directly, in this way, we only need the height of this tree. But this is a complete binary tree, not a perfect binary tree, but think about it in another way, if the height of the left subtree equals to right subtree, then we can know this is a perfect binary tree. Then we can use the previous formular.

So based on the above thought, we can compe up with the following algorithm.

*Python*

1 | def countNodes(root): |

For this method, the time complexity of it is `O(log(n)^2)`

.

Beacuse consider the worst case, there will always be one subtree that is not a perfect binary tree, so this is `O(log(n))`

, and every time we need to calculate the height of the current node, this costs `O(log(n))`

. In total, the time complexity is `O(log(n)log(n))`

.

From the math perspective(one perfect binary subtree, the other non-perfect):

T(n) = T(n/2) + c1 lgn

= T(n/4) + c1 lgn + c2 (lgn - 1)

= …

= T(1) + c [lgn + (lgn-1) + (lgn-2) + … + 1]

= O(lgn*lgn)

**P.S. 之前一直没有更新，现在想要一天更一篇。。。先试试哈。。。**