竞赛讨论区 > 【每日一题】7月6日精讲—平衡二叉树
头像
是瑶瑶呀
编辑于 2020-07-06 11:23
+ 关注

【每日一题】7月6日精讲—平衡二叉树

题号 NC19775
名称 平衡二叉树
来源 牛客国庆集训派对Day2
戳我进入往期每日一题汇总贴~
往期每日一题二期题单

图片说明

如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情

题解

要想让左子树点数-右子树点数的绝对值最大 ,我们可以把左子树尽量塞满,右子树用尽量少的节点。
左子树高度n-1,塞满的节点数为
右子树高度要尽量小,为n-1-d,然后对于右子树的每个子树,把子树的左子树高度拉满点数尽量小树,右子树的高度尽量小,这个过程显然是个递归的过程,即设f[i]为高度为i的“平衡”树的最小的点数,显然f[i] = 1+f[i-1]+f[i-d-1]。

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目7月13日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴

全部评论

(15) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐