# 222. Count Complete Tree Nodes

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

        # 完全二叉树的高度可以直接通过不断地访问左子树就可以获取
        # 判断左右子树的高度: 
        # 如果相等说明左子树是满二叉树, 然后进一步判断右子树的节点数(最后一层最后出现的节点必然在右子树中)
        # 如果不等说明右子树是深度小于左子树的满二叉树, 然后进一步判断左子树的节点数(最后一层最后出现的节点必然在左子树中)

class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # get the level of the tree
        def getLevel(node):
            treeLevel = 0
            while node:
                treeLevel += 1
                node = node.left
            return treeLevel
        treeLevel = getLevel(root)
        # print(treeLevel)
        
        if not root: return 0
        ld = getLevel(root.left)
        rd = getLevel(root.right)
        if ld == rd:
            return 2**ld + self.countNodes(root.right)
        else:
            return 2**rd + self.countNodes(root.left)
        
        
        # find the num of nodes in the last level
        # count = 0
        # out = False
        # def lastLevel(node, level, count, out):
        #     # global count
        #     # global out
        #     if out == True:
        #         return count
        #     if not node:
        #         return count
        #     if level<treeLevel and (not node.left or not node.right):
        #         out = True
        #         if node.left: count += 1
        #         return count
        #     if level==treeLevel: count += 1
        #     lastLevel(node.left, level+1, count, out)
        #     lastLevel(node.right, level+1, count, out)
        #     return count
        # count = lastLevel(root, 0, 0, False)
        # print(count)
        # return 2**(treeLevel-1)-1+count