首页 > 试题广场 >

完全二叉树结点数

[编程题]完全二叉树结点数
  • 热度指数：10307 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一棵完全二叉树的头节点head，返回这棵树的节点个数。

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

数据范围：节点数量满足 ，节点上每个值都满足
进阶：空间复杂度  ， 时间复杂度
示例1

输入

{1,2,3}

输出

3
示例2

输入

{}

输出

0

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
开通博客
头像 不会做题的小菜鸡
发表于 2021-07-17 14:55:45
精华题解 思路 最直观的思路就是将所有的结点数一遍，这样得到最终结果的时间代价就是O(N) 上面一个方法忽略了我们的树是完全二叉树这一性质，完全二叉树满足的特点就是要么是一个满二叉树，要么除了最后一层以外其它层全满，最后一层的叶子结点必须从左到右不间隔的排布。 虽然完全二叉树没有计算结点的方法 但是满二叉树 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 江南好___
发表于 2021-07-18 18:08:52
精华题解 描述 题目描述 给定一棵完全二叉树的头节点head，返回这棵树的节点个数。如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。 示例 输入：{1,2,3} 返回值：3知识点：完全二叉树，递归难度：⭐⭐⭐ 题解 方法一：递归 解题思路： 完全二叉树的特性： 完全二叉树的左右子树中至 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 棒棒糖🍭201906101800876
发表于 2021-07-15 19:11:00
精华题解 nc84. 求完全二叉树的高度 1. 思路一: (暴力做法, 不合要求) 直接递归统计二叉树的节点个数即可. 空树没有节点, 加上左子树和右子树的节点数就可以. class Solution { public: int nodeNum(struct TreeNode* head) { 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 草狐想
发表于 2021-01-11 16:32:47
思路： 先理解下面两点： 完全二叉树的子树也是完全二叉树 完全二叉树的左右子树中至少有一颗是满二叉树 计算一颗满二叉树节点个数： 1.计算一颗满二叉树节点个数很简单，就等于2^h - 1 , h为该满二叉树的高度 问题在于如何确定那颗子树是满二叉树 1.如果左子树的高度等于右子树高度+1， 展开全文
去ta的博客 赞 (18) 回复(2) 收起
头像 摸鱼学大师
发表于 2021-07-16 15:21:28
思路： 最简单的办法莫过于遍历所有的结点，统计个数，但是不管是哪种遍历，时间复杂度都要求至少为O(n)，因为要遍历每一个结点。 方法一：遍历法 不符合复杂度要求！！！ 方法二：二分法（利用性质） 由此，我们可以从完全二叉树的性质下手： 完全二叉树叶子结点只能出现在最下两层 最下层的叶子一定集中在左 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 总之就是非常可爱
发表于 2022-02-27 15:11:06
/** struct TreeNode {     int val;     struct TreeNode *left;     struct TreeNode *right;     TreeNode(int x) 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 总之就是非常可爱
发表于 2022-02-27 15:18:38
/** struct TreeNode {     int val;     struct TreeNode *left;     struct TreeNode *right;     TreeNode(int x) 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Maokt
发表于 2021-07-29 13:16:04
算法思想一：递归 解题思路： 完全二叉树的结点数量：根节点+左子树结点数量+右子树结点数 因此可以想到采用递归算法计算二叉树根结点的左右子树结点数量再加上根节点数量 代码展示： Python版本 class Solution:   &n 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 姐姐的遮阳伞
发表于 2022-03-27 14:09:27
import java.util.*; /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 小小小明哥
发表于 2022-01-19 03:38:10
该题目可以用二叉树的Morris遍历来实现空间复杂度为o(1),时间复杂度为o（n） /** struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 猫头鹰的咖啡馆
发表于 2021-10-27 16:38:22
/** struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right( 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 编程小鹏
发表于 2024-03-30 09:06:04
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int v 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Mr.galaxy
发表于 2022-11-22 21:55:20
">#include<vector> #include<algorithm> struct Tree {     int val;     struct T 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

二分 树
来自：面试常考算法题(二)
难度：
47条回答 8706浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号