我要招人

去企业版

首页 > 试题广场 >

完全二叉树结点数

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

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

算法知识视频讲解

Java

牛客148901号

public class Solution {

    public int nodeNum (TreeNode head) {
        if (head == null) {
            return 0;
        }
        return 1 + nodeNum(head.left) + nodeNum(head.right);
    }
}

发表于 2024-05-19 17:02:07 回复(0)

Java

牛客839384289号

public int nodeNum (TreeNode head) {
    // write code here
    int res=0;
    LinkedList<TreeNode> queue=new LinkedList<>();
    queue.add(head);
    while(!queue.isEmpty()){
        TreeNode node=queue.poll();
        if(node==null){
            return res;
        }else{
            res++;
            queue.add(node.left);
            queue.add(node.right);
        }
    }
    return res;
}

发表于 2024-03-24 13:26:35 回复(0)

Java

シkid~

我很好奇空间复杂度为O(1)的🙂

发表于 2022-03-02 21:01:16 回复(0)

Java

万里归途

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
}*/
import java.util.*;
public class Solution {
    public int nodeNum(TreeNode root) {
         // write code here
        if(root==null){
            return 0;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        int res=0;
        while(!queue.isEmpty()){
            int n=queue.size();
            res+=n;
            //ArrayList<Integer> tem=new ArrayList<>();
            for(int i=0;i<n;i++){
                TreeNode cur=queue.poll();
                //tem.add(cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
            //res.add(tem);
        }
        return res;
    }
}

发表于 2022-01-29 12:00:40 回复(1)

Java

知白鸭鸭

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
}*/
public class Solution {
    public int nodeNum(TreeNode head) {
        if(head == null)
            return 0;
        
        int left = getHight(head.left);
        int right = getHight(head.right);
        
        if(left != right){
            //左边不等于右边的高度，则必定左边高于右边，此时右边是满二叉树，计算公式为2^n-1,左边循环递归
            return 1+ (int)Math.pow(2,right)-1 + nodeNum(head.left);
        }else{
            return 1+(int)Math.pow(2,left)-1 + nodeNum(head.right);
        }
    }
    
    
    public int getHight(TreeNode head){
        int count =0;
        while(head != null){
            head = head.left;
            count++;
        }
        return count;
    }
}

发表于 2021-09-06 17:06:18 回复(0)

Java

se-rye

对 root 节点的左右子树进行高度统计，分别记为 left 和 right，有以下两种结果：

left == right。这说明，左子树一定是满二叉树，因为节点已经填充到右子树了，左子树必定已经填满了。所以左子树的节点总数我们可以直接得到，是 2^left - 1，加上当前这个 root 节点，则正好是 2^left。再对右子树进行递归统计。
left != right。说明此时最后一层不满，但倒数第二层已经满了，即右子树是满二叉树，可以直接得到右子树的节点个数。同理，右子树节点个数 + root 节点个数，总数为 2^right。再对左子树进行递归统计。

即明确在什么情况下左子树是满二叉树，这时候左子树的节点总数可以直接计算，右子树的节点总数通过递归计算；在什么情况下右子树是满二叉树，这时候右子树的节点总数可以直接计算，左子树的节点总数通过递归计算。

public class Solution {
    public int nodeNum(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = depth(root.left); // 左子树的高度
        int rightDepth = depth(root.right); // 右子树的高度
        if (leftDepth == rightDepth) {
            return (1 << leftDepth) + nodeNum(root.right); // 此时左子树一定是满的
        } else {
            // leftDepth != rightDepth
            return (1 << rightDepth) + nodeNum(root.left); // 此时右子树一定是满的
        }
    }
    
    public int depth(TreeNode node) {
        // 由于是完全二叉树，因此可以利用循环求深度
        int depth = 0;
        while (node != null) {
            depth++;
            node = node.left;
        }
        return depth;
    }
}

发表于 2021-08-25 01:07:10 回复(0)

Java

学习算法脑壳疼

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
}*/
import java.util.*;
public class Solution {
    public int nodeNum(TreeNode head) {
        if(head==null){
            return 0;
        }
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        int sum=0;
        queue.offer(head);
        while(!queue.isEmpty()){
            TreeNode temp=queue.poll();
            sum++;
            if(temp.left!=null){
                queue.offer(temp.left);
            }
            if(temp.right!=null){
                queue.offer(temp.right);
            }
        }
        return sum;
    }
}

发表于 2021-04-22 15:32:35 回复(0)

Java

看机会）p

/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}
}*/
public class Solution {
public int nodeNum(TreeNode head) {



int count = 0;
//头部判断
if(head == null){
return 0;
}

//头部操作就是计算为1，+1，

//模板，交给递归，递归一次就是1，，左边递归次数加右边递归次数。加head

count = nodeNum(head.left) +nodeNum(head.right) + 1;

return count;

}
}

发表于 2021-04-03 00:24:29 回复(0)

Java

牛客915296776号

public class Solution {
    public int nodeNum(TreeNode head) {
        // 满二叉树是特殊的完全二叉树，结点数量为2^k-1
        if (head == null) return 0;
        int cnt = 1;
        int leftHeight = checkHeight(head.left);
        int rightHeight = checkHeight(head.right);
        if (leftHeight > rightHeight) { // 左子树高度大于右子树，右子树一定是满二叉树
            cnt += Math.pow(2, rightHeight) - 1 + nodeNum(head.left);
        } else { // 左子树高度等于右子树，左子树一定是满二叉树
            cnt += Math.pow(2, leftHeight) - 1 + nodeNum(head.right);
        }
        return cnt;
    }
    
    // 计算树高度
    private int checkHeight(TreeNode head) {
        if (head == null) return 0;
        int height = 0;
        while (head != null) {
            height++;
            head = head.left;
        }
        return height;
    }
}

发表于 2021-02-17 15:55:30 回复(0)

Java

牛客119190309号

public class Solution {
public int nodeNum(TreeNode head) {
if(head==null){
return 0;
}else if(head.left!=null && head.right==null){
return 1+nodeNum(head.left);
}else if(head.left==null && head.right!=null){
return 1+nodeNum(head.right);
}else{
return 1+nodeNum(head.left)+nodeNum(head.right);
}
}
}

发表于 2020-09-19 23:28:53 回复(0)