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.
计算完全二叉树的节点数，如果直接遍历并计算的话会是O(n)的时间复杂度。
能不能充分利用完全二叉树的特性呢
如果从一个根节点开始一直向左和一直向右的深度是相等的，那么意味着这个根节点下面的数是满二叉树，其节点数直接可以算出来。
我们从根节点开始检查，如果不是满二叉树就往下递归，每找到一颗满二叉树就直接返回节点数。
var countNodes = function(root) {
//获取二叉树一直向左或向右的高度
var getHeight = function(root,flag) {
var count = 0;
if (flag) {
while (root.left) {
count++;
root = root.left;
}
} else {
while (root.right) {
count++;
root = root.right;
}
}
return count;
};
if (!root)
return 0;
var l = getHeight(root,true);
var r = getHeight(root,false);
if (l===r) {
//如果左右高度相等，节点数等于2^树高-1
return (2<<l) - 1;
} else {
//如果不等就递归
return countNodes(root.left) + countNodes(root.right) + 1;
}
};
