完全二叉树结点数

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

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

算法知识视频讲解

Javascript

nicole27

function nodeNum( head ) {
    // write code here
    let queue = [];
    let count = 0;
    if(head==null) return count;
    queue.push(head);
    while(queue.length>0){
        let len = queue.length;
        count = len+count;
        while(len--){
            let node = queue.shift();
            if(node.left) queue.push(node.left);
            if(node.right) queue.push(node.right);
        }
    }
    return count;
}

发表于 2022-03-25 16:33:33 回复(0)

JavaScript

别卷啦！

不讲码德的递归写法

function nodeNum( head ) {
    // write code here
    if(!head) return 0
    return 1 + nodeNum(head.left) + nodeNum(head.right)
}
module.exports = {
    nodeNum : nodeNum
};

发表于 2020-12-31 17:45:24 回复(0)