目录

0222:完全二叉树的节点个数

力扣第 222 题

题目

给你一棵 完全二叉树 的根节点 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) 的简单解决方案。你可以设计一个更快的算法吗?

相似问题:

分析

递归很简单,要求比 O(N) 更快,考虑二分:

  • 先遍历到最底层最左边的节点,得到高度 h
  • 该完全二叉树的节点数 x 必然满足 x<=2^h-1
  • 以节点数 x 为界,序号 [1, x] 的节点都存在,序号 [x+1, 2^h-1] 都不存在
  • 因此可以二分查找 x 是否存在
  • 判断序号 x 是否存在,可以按 x 的二进制遍历树

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        def check(x):
            p = root
            for bit in bin(x)[3:]:
                p=p.left if bit=='0' else p.right
                if not p:
                    return True
            return False
        h,p = 0,root
        while p:
            p=p.left
            h+=1
        return bisect_left(range(1<<h),True,(1<<h)//2,key=check)-1

52 ms