I seemed to have the fastest time submission(!), so sharing my code.
The code works by first computing the height of the tree by iterating down the left side in log(n) time.
Then it does a binary search down the left and right sub-trees by checking each time whether the height of the right subtree is equal to the overall height expected. There will be log(n) checks each taking log(n) time to check the height for a total of log(n)^2 time.
class Solution(object): def countNodes(self, root): def contains(node, h): for _ in range(h): node = node.left return node if not root: return 0 h, curr = 0, root while curr.left: h, curr = h + 1, curr.left curr, cnt = root, 1 while h: if contains(curr.right, h-1): curr, cnt = curr.right, cnt*2+1 else: curr, cnt = curr.left, cnt*2 h-=1 return cnt