Given a complete binary tree, count the number of nodes.
Note: 
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Example:
Input: 
    1
   / \
  2   3
 / \  /
4  5 6
Output: 6
# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def countNodes(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         if not root:
             return 0
         h = height(root)
         res = 0
         while root:
             if height(root.right) == h-1:
                 res += 1<<h
                 root = root.right
             else:
                 res += 1<<(h-1)
                 root = root.left
             h -= 1
             
         return res
 
 def height(node):
     if not node:
         return -1
     else:
         return 1+height(node.left)
# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def countNodes(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         if not root:
             return 0
         h = height(root)
         res = 0
         while root:
             if height(root.right) == h-1:
                 res += 1<<h
                 root = root.right
             else:
                 res += 1<<(h-1)
                 root = root.left
             h -= 1
             
         return res
 
 def height(node):
     if not node:
         return -1
     else:
         return 1+height(node.left)