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