After so many failed trial with recursion from both sides, I saw a previous post and found the way to reduce to one recursion and got accepted. It is not fair while other language can get accepted with two recursions, but python is just slow..

```
class Solution:
def getheight(self, root):
count = 0
while root:
root = root.left
count += 1
return count
# @param {TreeNode} root
# @return {integer}
def countNodes(self, root):
if not root:
return 0
h = self.getheight(root.left)
h_subright = self.getheight(root.right)
if h == h_subright:
return 2 ** h + self.countNodes(root.right)
else:
return self.countNodes(root.left) + 2 ** (h - 1)
```