首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
高度为1的平衡二叉树节点为1个,高度为5的最少多少个?
[单选题]
高度为1的平衡二叉树节点为1个,高度为5的最少多少个?
10
11
12
13
添加笔记
邀请回答
收藏(358)
分享
纠错
10个回答
添加回答
13
推荐
eagle
C
平衡二叉树
是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
高度为5的话, 根的左子树高4, 右子树高3
经推倒可以得出,高度与最小节点数对应关系是:
1 -> 1
2 -> 2
3 -> 4
4 -> 7
5 -> 12
编辑于 2019-05-05 14:23:19
回复(0)
25
Llike
发表于 2019-08-13 14:42:45
回复(0)
10
章鱼fun
C F(N) = F(N-1)+ F(N-2)+1
F(0)=0,F(1) = 1
发表于 2015-04-11 12:11:44
回复(0)
6
__sgf__
F(N) = F(N-1)+ F(N-2)+1 ; F(0)=0,F(1) = 1 ;所以值为0-1-2-4-7-12......
编辑于 2022-03-22 15:04:08
回复(1)
2
蒙奇
推导类似斐波那契~eagle有详细说明
选C--12
发表于 2015-09-07 15:25:56
回复(0)
1
牛客694853220号
c
平衡二叉树要求左右两个子树的高度差不超过1,或者为一个空树(n=0)。
因此平衡二叉树的最小节点数
c
1
->1
c
2
->2
c
3
->c
1
+c
2
+1=4
c
4
->c
2
+c
3
+1=7
....
c
n
->c
n-2
+c
n-1
+1
发表于 2022-07-01 10:29:04
回复(0)
0
牛客130365080号
类似于斐波那契数列, 高度为n的树需要的节点总数为f(n)
但是f(n)=f(n-2)+f(n-1)+1,这个1是根节点本身
f(0)=0
f(1)=1
发表于 2023-10-14 16:34:56
回复(0)
0
XInobukiki
0-1-2-4-7-12
发表于 2022-03-19 15:12:56
回复(0)
0
Eva.yx.wang
假设高度为h的二叉平衡树至少有S(h)个节点,则S(h)=1+S(h-1)+S(h-2),变形为S(h)+1=(S(h-1)+1)+(S(h-2)+1)。而斐波那契数列满足fib(h+2)=fib(h+1)+fib(h),因此有S(h)+1=fib(h+2),带入树高h=5,可得S(5)=12
发表于 2022-03-19 01:50:55
回复(0)
0
Sophia_Beta
<p>只有一个根结点高度是1</p>
发表于 2020-05-31 16:55:26
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
搜狐
树
上传者:
小小
难度:
10条回答
358收藏
16886浏览
热门推荐
相关试题
程序设计(可用任何编程语言实现) ...
搜狐
数组
排序
评论
(8)
程序设计(可用任何编程语言实现) ...
搜狐
字符串
评论
(3)
有同事不完成任务,影响力进度,你怎...
业务综合
评论
(1)
你身边有哪些人还没有使用滴滴,你认...
用户研究
评论
(1)
怎么做一个需求
需求分析
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题