【每日一题】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. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴