As I mentioned, the key to this problem is at least one of the subtrees is a perfect tree, full complete tree, or both of them are.

Thus, by using O(lgn) time, which is for finding the "height", I can reduce the problem to n/2, or at most 2n/3? (I'm not so sure) So the total time complexity is O(lgn * lgn) !

```
public class Solution {
public int countNodes(TreeNode root) {
if (root == null) return 0;
int left = findHeight(root.left);
int right = findHeight(root.right);
return left == right ? (1 << left) + countNodes(root.right) : (1 << right) + countNodes(root.left);
}
private int findHeight(TreeNode root) {
int height = 0;
while (root != null) {
root = root.left;
height++;
}
return height;
}
}
```

My first time to explain my code, hope it helps and open to any comments. ^_^