给定一棵完全二叉树的头节点head，返回这棵树的节点个数。
完全二叉树指：设二叉树的深度为h，则 [1,h-1] 层的节点数都满足 
个
数据范围：节点数量满足 
，节点上每个值都满足 
进阶：空间复杂度 )
， 时间复杂度 )
[编程题]完全二叉树结点数
class Solution {
public:
int nodeNum(struct TreeNode* head)
{
int nodeNum = 0;
int allHeight = 0, rightHeight = 0;
while (nullptr != head)
{
allHeight = height(head);
rightHeight = height(head->right);
head = allHeight == rightHeight + 1 ? head->right
: head->left;
nodeNum += (1 << (rightHeight));
}
return nodeNum;
}
private:
// 统计完全二叉树的高度
int height(TreeNode *head)
{
int count = 0;
while (nullptr != head)
{
head = head->left;
count++;
}
return count;
}
};
发表于 2016-03-07 08:14:59
回复(0)
class Solution {
public:
int nodeNum(struct TreeNode* head) {
if (!head) return 0;
return 1 + nodeNum(head->left) + nodeNum(head->right);
}
};
发表于 2021-07-08 16:29:09
回复(0)
根据完全二叉树的定义，可以发现其左右子树必定有一个是满二叉树，因此可以利用二分解决
/**
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
int get_height(struct TreeNode *head){
return head == NULL ? 0 : get_height(head->left) + 1;
}
int nodeNum(struct TreeNode* head) {
if(head == NULL)
return 0;
int height = get_height(head);
int cur_h = 1;
if(head->right != NULL){
struct TreeNode *new_head = head->right;
cur_h++;
while(new_head->left != NULL){
new_head = new_head->left;
cur_h++;
}
}
if(cur_h == height)
return pow(2, height-1) + nodeNum(head->right);
else
return pow(2, cur_h-1) + nodeNum(head->left);
}
};
发表于 2020-09-05 01:47:51
回复(0)
这道题直接遍历，是绝对可以做到的，时间复杂度O(N)没什么好说的
public class Solution {
int nodeCount = 0;
public int nodeNum(TreeNode head) {
count(head);
return nodeCount;
}
public void count(TreeNode root) {
if(root != null){
nodeCount ++;
count(root.left);
count(root.right);
}
}
} 但其实我们有更好的方法来进行优化，假设整棵树的深度为h（只要溜一遍树的左边界就可以得到），我们每次考虑右树最左的节点有没有到整棵树的最深层。 - 如果到了最深层，由于完全二叉树建树时按照从上往下从左往右的顺序排列节点，因此左树一定是满二叉树，节点数为2h-1-1，加上头结点就是2h-1个节点，由于右树状况还不清楚，再递归计算右树的节点数；
- 如果没有到最深层，由于左树深度比它深一层，而完全二叉树在建树时按照从上往下从左往右的顺序排列节点，说明更浅的右树一定已经排满了，是满二叉树。而右树的高度为h-2，节点数为2h-2个，由于左树状况还不清楚，再递归计算左树的节点数。
public class Solution {
public int nodeNum(TreeNode head) {
if(head == null) return 0; // 空树返回0
return bs(head, 1, mostLeftLevel(head, 1));
}
// 计算node为根的子树最深可以到达哪一层，level为node节点所在层号
private int mostLeftLevel(TreeNode node, int level) {
while(node != null){
level ++;
node = node.left;
}
return level - 1;
}
// node在第level层，h为树深
private int bs(TreeNode node, int level, int h){
if(level == h) return 1;
if(mostLeftLevel(node.right, level + 1) == h){
// 右树的最左节点到底了，左树一定是满二叉树，右树递归
return (1 << (h - level)) + bs(node.right, level + 1, h);
}else{
// 右树的最左节点没到底，右树一定是满二叉树，左树递归
return (1 << (h - level - 1)) + bs(node.left, level + 1, h);
}
}
} 分析一下整个算法的复杂度。假如bs函数来到了1层，只会走一个分支，在进入分支之前会计算一次右树最左节点的深度，计算深度时level已经自增了1，只会遍历h-1个节点；如果来到了第二层，又需要计算深度，level在1层的基础上又自增了1，只会遍历h-2个节点；以此类推其实是等差数列的求和，时间复杂度为O(h2)=O((logN)2)。
发表于 2021-11-28 10:03:27
回复(0)
解法一：最简单的做法当然是直接递归搜索所有节点，然后计数，如下：
public int nodeNum(TreeNode head) {
if(head == null) return 0;
int leftCnt = nodeNum(head.left) + 1;
int rightCnt = nodeNum(head.right) + leftCnt;
return rightCnt;
} 解法二：也可以通过递归搜索所有的节点，思路如下：
1. 对于每个节点，都要判断它是不是全满的节点
2. 如果是全满节点，直接代入公式计算节点数
3. 如果不是全满的节点，则判断是左边非全满，还是右边非全满，因为左边和右边节点的所有子节点是独立的，最后一个叶子结点不可能既属于左边节点，又属于右边节点
4. 找到非全满的节点，继续递归运算，重复上述过程，即：全满的带公式，非全满的继续找他的全满节点
5. 直到递归到最小节点（再无左右节点），开始回溯, 累计节点数， 代码如下：
public static int getHeight(TreeNode head) {
return head == null ? 0 : getHeight(head.left) + 1;
}
public static int nodeNum(TreeNode head) {
if (head == null)
return 0;
// 求出高度
int height = getHeight(head);
int curHeight = 1;
if (head.right != null) {
TreeNode newHead = head.right;
curHeight++;
while (newHead.left != null) {
newHead = newHead.left;
curHeight++;
}
}
if (curHeight == height)
// 说明当前的 head 左边是满的,则不满的在右边
return (int) Math.pow(2, height - 1) + nodeNum(head.right);
else
// 高度不一致，则说明右边是满的，则说明不满的在左边
return (int) Math.pow(2, curHeight - 1) + nodeNum(head.left);
}
发表于 2024-06-07 17:12:51
回复(0)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
#include <queue>
class Solution {
public:
/**
层序遍历，一边遍历一边计数
*/
int nodeNum(TreeNode* head) {
int ans = 0;
queue<TreeNode*>lab;
lab.push(head);
while (!lab.empty()) {
TreeNode* temp = lab.front();
lab.pop();
if (temp) {
ans++;
lab.push(temp->left);
lab.push(temp->right);
}
}
return ans;
}
};
编辑于 2024-04-12 14:18:28
回复(0)
using System;
using System.Collections.Generic;
/*
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode (int x)
{
val = x;
}
}
*/
class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head TreeNode类
* @return int整型
*/
public int nodeNum (TreeNode head) {
// write code here
int nCount = 0;
if (head == null)
return nCount;
nCount++;
return nCount + nodeNum(head.left) + nodeNum(head.right);
}
}
发表于 2024-03-29 22:36:14
回复(0)
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)
if not head: return 0 return self.nodeNum(head.left)+1+self.nodeNum(head.right) #递归
发表于 2024-03-07 00:36:23
回复(0)
/**
* #[derive(PartialEq, Eq, Debug, Clone)]
* pub struct TreeNode {
* pub val: i32,
* pub left: Option<Box<TreeNode>>,
* pub right: Option<Box<TreeNode>>,
* }
*
* impl TreeNode {
* #[inline]
* fn new(val: i32) -> Self {
* TreeNode {
* val: val,
* left: None,
* right: None,
* }
* }
* }
*/
struct Solution{
}
impl Solution {
fn new() -> Self {
Solution{}
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head TreeNode类
* @return int整型
*/
pub fn nodeNum(&self, mut head: Option<Box<TreeNode>>) -> i32 {
// write code here
if head.is_none() {0} else {
1 +
self.nodeNum(head.as_mut().unwrap().left.take()) +
self.nodeNum(head.as_mut().unwrap().right.take())
}
}
}
发表于 2023-08-31 21:07:32
回复(0)
/**
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<>();
queue.add(head);
int sum=0;
while(!queue.isEmpty()){
int size=queue.size();
sum+=size;
for(int i=0;i<size;i++){
TreeNode node=queue.poll();
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
}
return sum;
}
}
发表于 2023-05-16 10:13:53
回复(0)
package main
import . "nc_tools"
/*
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
*
* @param head TreeNode类
* @return int整型
*/
func nodeNum( head *TreeNode ) int {
ans:=0
var order func(*TreeNode)
order=func(root *TreeNode){
if root==nil{
return
}
ans++
order(root.Left)
order(root.Right)
}
order(head)
return ans
}
发表于 2023-03-09 00:01:24
回复(0)
因为是完全二叉树，直接数最后一层的个数就行了，最后一层的个数等于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)
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)
/**
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)
问题信息
通过挑战的用户
查看代码-
2022-11-29 15:05:15
-
2022-09-19 15:42:09
-
2022-09-16 10:26:43
-
2022-09-16 00:27:19
-
2022-09-15 11:34:10
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
