leetcode222求完全二叉树节点个数

#(0,0,0),(0,0,1)(0,1,0)(0,1,1)(1,0,0)(1,0,1)(1,1,0)(1,1,1)其实是
0，1，2，3，4，5，6，7

# 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 findlevel(self, root):
        if root:
             return 1+self.findlevel(root.left)
        else:
            return 0
    '''step就是用1代表(0,0,1),3'''  
    def findendNode(self, root, step, level):
        #print step,level
        temp = root
        for i in range(level):
            if ((step&(2**(level-1-i))) >> (level-1-i)) == 0:
                #print 'xxx'
                temp = temp.left
            else:
                temp = temp.right
        if temp:
            return True
        else:
            return False
                
    '''
    def findendNode(self, root, step, level):
        temp = root
        lr = list(bin(step))[2:]
        #print 'lr', lr, 'level', level
        lrlen = len(lr)
        # 左子树
        for i in range(level-lrlen):
            temp = temp.left
        for i in range(lrlen):
            if lr[i] == '0':
                temp = temp.left
            else:
                temp = temp.right
        if temp:
            return True
        else:
            return False
    '''    
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        level=self.findlevel(root)-1
        if level == 0:
            return 1
        endend = 2**level
        s = endend - 1
        # 找出深度后呢，找出结尾，看下结尾排列，看下h = 3最后一排的排列,0代表向左子树搜索，1代表向右子树搜索，可以用bit特         # 位表示，可以用二分查找法
        #(0,0,0),(0,0,1)(0,1,0)(0,1,1)(1,0,0)(1,0,1)(1,1,0)(1,1,1)其实就是0，1，2，3，4，5，6，7
        start = 0
        end = endend-1
        while True:
            # 从中间找
            temp = (end+start)/2
            if not self.findendNode(root, temp, level):
                # 如果是false，设置为end
                end = temp
            else:
                # 如果是true，设置为起点
                start = temp
            if end-start == 1:
                if end == endend-1:
                    if self.findendNode(root, end, level):
                        s += endend
                        return s
                    else:
                        s+= end
                        return s
                else:
                    s += end
                    return s