title
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6]
输出：6
示例 2：
输入：root = []
输出：0
示例 3：
输入：root = [1]
输出：1
提示：
- 树中节点的数目范围是
[0, 5 * 104] 0 <= Node.val <= 5 * 104- 题目数据保证输入的树是 完全二叉树
进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？
solution
二分。已知结果范围，对结果进行二分。
class Solution:
def countNodes(self, root: TreeNode) -> int:
if not root:
return 0
height = 0
p = root
while p:
height += 1
p = p.left
# print(height)
left, right = (1 << (height - 1)), (1 << height) - 1
# print(left, right)
while left <= right:
mid = (right - left) // 2 + left
if self.exist(root, mid, height):
left = mid + 1
else:
right = mid - 1
return right
def exist(self, root: TreeNode, k: int, height: int):
if height == 1:
return root is not None
bits = 1 << (height - 2)
while root and bits > 0:
if bits & k == 0:
root = root.left
else:
root = root.right
bits >>= 1
return root is not None