I know there is already a high rated answer here https://discuss.leetcode.com/topic/15533/concise-java-solutions-o-log-n-2. Just share concise C++ codes based on the same idea: one of left or right subtree is PERFECT tree (whose node count is a math), the other can be solved by a "recursive" call. Below are a pure recursive solution and a pure iterative solution.

**1. Recursive solution**

```
class Solution {
private:
int getHeight(TreeNode * root) {
return root == NULL ? 0 : 1 + getHeight(root->left);
}
int calPerfectTree(int h) {
return (1<<h) - 1;
}
int count(TreeNode * root, int h) {
if (!root) return 0;
int rh = getHeight(root->right);
return (rh == h - 1) ? 1 + calPerfectTree(h-1) + count(root->right, h-1) : 1 + calPerfectTree(h-2) + count(root->left, h-1);
}
public:
int countNodes(TreeNode* root) {
return count(root, getHeight(root));
}
};
```

**2. Iterative solution**

```
class Solution {
private:
int getHeight(TreeNode * root) {
int h = 0;
for (; root != NULL; h++, root = root->left);
return h;
}
int calPerfectTree(int h) {
return (1<<h) - 1;
}
public:
int countNodes(TreeNode* root) {
int res = 0, h = getHeight(root), rh;
while (root) {
rh = getHeight(root->right);
res += 1 + ((rh == h - 1) ? calPerfectTree(h-1) : calPerfectTree(h-2));
root = (rh == h - 1) ? root->right : root->left;
--h;
}
return res;
}
};
```