```
class Solution {
public:
int countNodes(TreeNode* root) {
if(!root) return 0;
TreeNode* p=root;
int lcnt=0;
while(p){
p=p->left;
lcnt++;
}
TreeNode* q=root;
int rcnt=0;
while(q){
q=q->left;
rcnt++;
}
if(lcnt==rcnt) return (1<<lcnt)-1;
p=root->left;
int lrcnt=1;
while(p){
p=p->right;
lrcnt++;
}
if(lrcnt==lcnt){
return (1<<(lcnt-1))+countNodes(root->right);
}else{
return countNodes(root->left)+(1<<(rcnt-1));
}
}
};
```

maybe is a little long, but very clear logic, I just use divide and conque, I find that it must can be divided into a complete tree and a full tree(left or right substree is full tree), and it depends on whether the right most node of left substree is in the last level or not, so three O(h) traverse and divide and conquer