222. Count Complete Tree Nodes

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;
    }
};