```
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == NULL)
return 0;
int height = 0;
int cnt = 0;
TreeNode *left = root->left;
TreeNode *right = root->left;
while(right != NULL)
{
height++;
left = left->left;
right = right->right;
}
cnt = (1 << height) - 1;
/* <left == NULL && right == NULL> denotes the left subtree of root must be a perfect binary tree. The right subtree? May be,may be not.
* <left != NULL && right == NULL> denotes the right subtree of root must be a perfect binary tree. Similarly,it's not clear whether the left is
* a perfect binary tree.
* cnt denotes the number of nodes in the perfect binary tree, 1 denotes the root
*/
if (left == NULL)
return 1 + cnt + countNodes(root->right);
return 1 + cnt + countNodes(root->left);
}
};
```