[nowCoder]完全二叉树结点数

class Solution {
private:
        int calcHeight(TreeNode *head)
        {  
            int height = 0;
            while(head)
            {  
                head = head->left;
                height ++;
            }  
            return height;
        }  
    public:
        int nodeNum(struct TreeNode* head)
        {  
            if(head == NULL)
                return 0;
 
            int height = calcHeight(head);
            //cout <<"height\t" <
 
            if(calcHeight(head->right) == height - 1)//left sub-tree is full
                return (1 <<(height - 1) )+ nodeNum(head->right);
            else// right sub-tree is full
                return (1 <<(height - 2) )+ nodeNum(head->left);
        }
};