Below is my Java solution, after inspiration from some of the answers on this forum and working out the problem by hand.

For those who don't want to look at the code below directly, here's a pointer: **Analyze simple 4, 5 and 6 node trees.** Covering these three cases covers ** ALL** cases.

My code is as below:

```
public class Solution {
private int totalNodes = 0;
public int countNodes(TreeNode root) {
if(root == null) return 0;
totalNodes = 0;
count(root);
return totalNodes;
}
private void count(TreeNode node) {
if(node.left == null && node.right == null) {
totalNodes += 1;
return;
}
if(height(node.left) == height(node.right)) {
totalNodes += (1 << height(node.left));
if(node.right != null) count(node.right);
} else {
totalNodes += (1 << height(node.right));
if(node.left != null) count(node.left);
}
}
private int height(TreeNode node) {
if(node == null) return 0;
int height = 1;
TreeNode tmp = node;
while(tmp != null) {
tmp = tmp.left;
height++;
}
return height-1;
}
}
```

Two key differences from other answers I've observed on this topic here:

- I've used a private variable, to store final counts instead of

passing around an argument to recursion. I thought this would be

much cleaner. - I've sped up my computation by using the bit-shift operator <<. As a side note, if you replace this with Math.pow(2, ...), LeetCode OJ throws a "Time limit exceeded" error. :)

Also, in the beginning of the `count()`

method, you can see the termination condition laid out very simply: If a node is ever reached, where it has no more children, increment totalNodes by 1 and exit.