义气奇异果

文章
4
资源
0
加入时间
3年0月27天

牛客每日一题 平衡二叉树 题解(dp)

题目链接题目思路感觉这种题目对于我来说完全没思路。。。。哭了要想让左子树点数-右子树点数的绝对值最大 ,我们可以把左子树尽量塞满,右子树用尽量少的节点。左子树高度n-1,塞满的节点数为2^(n-1)-1右子树高度要尽量小,为n-1-d,然后对于右子树的每个子树,把子树的左子树高度拉满点数尽量小树,右子树的高度尽量小,这个过程显然是个递归的过程,即设f[i]为高度为i的“平衡”树的最小的点数,显然f[i] = 1+f[i-1]+f[i-d-1]。代码#include<cstdio&a