完全二叉树结点数

[编程题]完全二叉树结点数

热度指数：10673 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵完全二叉树的头节点head，返回这棵树的节点个数。

完全二叉树指：设二叉树的深度为h，则 [1,h-1] 层的节点数都满足 $2^{i-1}$ 个

数据范围：节点数量满足 $0 \le n \le 100000$ ，节点上每个值都满足 $0 \le val \le 100000$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

{1,2,3}

输出

示例2

输入

{}

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python3

牛客765331463号

if not head:
    return 0
return self.nodeNum(head.left)+1+self.nodeNum(head.right) #递归

发表于 2024-03-07 00:36:23 回复(0)

Python3

E-Doz

因为是完全二叉树，直接数最后一层的个数就行了，最后一层的个数等于2**height - （遇到的叶子节点个数）
class Solution:
    count = 0
    def nodeNum(self , head: TreeNode) -> int:
        # write code here
        def height(head):
            if not head:
                self.count += 1
                return 0
            return max(height(head.left), height(head.right)) + 1
        h = height(head)
        ret = 0
        for i in range(h):
            ret += 2**i
        lastLevel = 2**h
        return ret - (lastLevel - self.count)

发表于 2022-09-29 02:24:11 回复(0)