• 27.1%

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

Definition of a complete binary tree from Wikipedia:

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.

，如果完全二叉树是满二叉树，就只这个结果。如果不是，就递归，两个相加。

https://discuss.leetcode.com/topic/15515/easy-short-c-recursive-solution

Easy short c++ recursive solution

https://discuss.leetcode.com/topic/31457/a-very-clear-recursive-solution-isn-t-it

A very clear recursive solution, isn’t it?

https://discuss.leetcode.com/topic/19215/simple-c-recursive-solution

Simple C++ recursive solution

https://discuss.leetcode.com/topic/23830/68ms-c-solution-using-binary-search-with-brief-explanation

68ms C++ solution using binary search with brief explanation.

The thought is simple. We just consider the lowest level of the tree.

The left child and right child just divide the tree lower than the current node to 2 part.

So what this code do is first check the right most child of the current node’s left child.

If this child is exist, we know that there may be more nodes on the right side of the tree. So we move the current node to it’s right child. And repeat until we reach the lowest level.

https://discuss.leetcode.com/topic/17971/my-python-solution-in-o-lgn-lgn-time

My python solution in O(lgn * lgn) time

compare the depth between left sub tree and right sub tree.

A, If it is equal, it means the left sub tree is a full binary tree

B, It it is not , it means the right sub tree is a full binary tree