完全二叉树结点数

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

热度指数：10320 时间限制：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，点此查看相关信息

算法知识视频讲解

Python 3

Joy_9

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        #Method 2
        self.final=0
        if not(root):
            return 0
        def max_depth(root):
            if not root:
                self.final+=1
                return 0
            return max(max_depth(root.left),max_depth(root.right))+1
        max_v=max_depth(root)

        return int(2**(max_v-1)-1+(self.final-2**(max_v-1)))
        #Method 1
        class Solution:
    def countNodes(self, root: TreeNode) -> int:
        res=[]
        def preorder(root):
            if not root:
                return
            res.append(res.append)
            preorder(root.left)
            preorder(root.right)
        preorder(root)

        return len(res)

发表于 2022-01-21 12:39:44 回复(0)

Python 3

HHHChen77

class Solution:
    def nodeNum(self , head ):
        # 完全二叉树的结点数计算
        if not head:
            return 0
        # 判断完美二叉树
        l, r = head, head
        # 左/右侧深度
        l_c, r_c = 0, 0
        while l:
            l = l.left
            l_c += 1
        while r:
            r = r.right
            r_c += 1
        # 若为完美二叉树,是则可根据深度计算得到结点数
        if l_c == r_c:
            return 2**l_c - 1
        # 不是完美二叉树,则进行常规递归计算左/右子树的结点数
        left = self.nodeNum(head.left)
        right = self.nodeNum(head.right)
        # 返回总结点数
        return 1 + left + right

发表于 2021-09-19 10:39:06 回复(0)

Python 3

牛客35961088号

class Solution:
    def nodeNum(self , head ):
        # write code here
        ## 层序遍历
        stack = [head]
        L = 0
        while stack:
            l = len(stack)
            for i in range(l):
                r = stack.pop(0)
                if not r:
                    return L
                else:
                    L += 1
                    stack.append(r.left)
                    stack.append(r.right)
        return L

发表于 2021-07-29 17:26:14 回复(0)