 I try to use iterative method rather than recursive for saving time.
 Try to use << rather than pow() function.

Just look at this tree. If we use left node and right node to reach their leftend respectively, we can compare the heights and find out which part is losing rightend.

For this tree, we first use node2 and node3 and find that the length of their leftend is the same, so we can deduce that we only need to search the right node. So we set root as root>right.

Repeat above algorithm and then we find that the left is longer than right, so we only need to search the left part of the node.

Until root == NULL.

As for counting the nodes, if height of left node > right node, it means that the right node is a full tree, so we set res += 1 << right_count; else we will set res += 1 << left_count.
Code:
class Solution {
public:
int countNodes(TreeNode* root) {
if(root == NULL) return 0;
int res = 0;
while(root){
int lcount = 0, rcount = 0;
for(TreeNode* pleft = root>left; pleft; pleft = pleft>left){lcount++;}
for(TreeNode* pright = root>right; pright; pright = pright>left){rcount++;}
if(lcount > rcount){
root = root>left;
res += 1 << rcount;
}else{
root = root>right;
res += 1 << lcount;
}
}
return res;
}
};
Time: