# LeetCode 222. Count Complete Tree Nodes – 二分查找（Binary Search）系列题13

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

Example 1:

Input: root = [1,2,3,4,5,6]
Output: 6

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

Constraints:

• The number of nodes in the tree is in the range [0, 5 * 104].
• 0 <= Node.val <= 5 * 104
• The tree is guaranteed to be complete.

class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
h = self.height(root)
if h <= 1:
return h

#前h-1层的总个数
res = 2 ** (h - 1) - 1

#最后一层个数介于[1, 2 ** (h - 1)]之间
l, r = 1, 2 ** (h - 1)

while l <= r:
#并判断最后一层中间那个节点是否存在
mid = l + (r - l) // 2
if self.isExist(root, h): #如存在则继续查找右半区间即右子树
l = mid + 1
if root:
root = root.right
else:   #如不存在则继续查找左半区间即左子树
r = mid - 1
if root:
root = root.left
#左右半区间分别对应于左右子树，子树高度减1
h -= 1

#查找到最后，l是最后一层第一不存在的节点，因此最后一层个数是l - 1
return res + l - 1

def height(self, root):
res = 0
while root:
root = root.left
res += 1

return res

#判断一棵高度为h的树的最后一层的中间节点是否存在
def isExist(self, root, h):
#只有一层时即最后一层，直接判断该节点是否存在
if h == 1:
return root != None

#如果不只一层则最后一层的中间节点是左子树的最靠右的那个节点
root = root.left
h -= 1
for i in range(h - 1):
root = root.right

return root != None

THE END

)">