首页 > 试题广场 >

高度为1的平衡二叉树节点为1个，高度为5的最少多少个？

[单选题]
高度为1的平衡二叉树节点为1个，高度为5的最少多少个？ 
  • 10
  • 11
  • 12
  • 13
添加回答
推荐
eagle头像 eagle
C

平衡二叉树是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

高度为5的话， 根的左子树高4， 右子树高3
经推倒可以得出，高度与最小节点数对应关系是：
1 -> 1
2 -> 2
3 -> 4
4 -> 7
5 -> 12
编辑于 2019-05-05 14:23:19 回复(0)
Llike头像 Llike
发表于 2019-08-13 14:42:45 回复(0)
章鱼fun头像 章鱼fun
C   F(N) = F(N-1)+ F(N-2)+1
F(0)=0,F(1) = 1
发表于 2015-04-11 12:11:44 回复(0)
__sgf__头像 __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)
蒙奇头像 蒙奇
推导类似斐波那契~eagle有详细说明
选C--12
发表于 2015-09-07 15:25:56 回复(0)
牛客694853220号头像 牛客694853220号
c
平衡二叉树要求左右两个子树的高度差不超过1，或者为一个空树（n=0)。
因此平衡二叉树的最小节点数
c1->1
c2->2
c3->c1+c2+1=4
c4->c2+c3+1=7
....
cn ->cn-2+cn-1+1
发表于 2022-07-01 10:29:04 回复(0)
牛客130365080号头像 牛客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)
XInobukiki头像 XInobukiki
0-1-2-4-7-12
发表于 2022-03-19 15:12:56 回复(0)
Eva.yx.wang头像 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)
Sophia_Beta头像 Sophia_Beta
<p>只有一个根结点高度是1</p>
发表于 2020-05-31 16:55:26 回复(0)
提交观点

问题信息

北京搜狐互联网信息服务有限公司 树
上传者：小小
难度：
10条回答 17204浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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