【每日一题】 7-6 平衡二叉树

题意：

给定平衡二叉树的高度，并且给定平衡因子，求这颗树中所有结点的左右子树的节点数之差

做法：

一开始看错了题意，以为是根节点的左右子树之差，然后直接左子树满二叉树，右子树一条链，WA到自闭，然后发现是所有结点的左右子树，所以考虑构造出一条链高度为 n 并且他的另一个子树满足与他的长度差为 d 的树，这样可以很容易的推出公式

$dp_n=dp_{n-1}+dp_{n-d-1}+1$ ，然后直接套用这个公式递归就可以得到答案了，不过需要注意这里的 d 可能比较大，但是按照题意，d 最大只能是 n-1，所以我们先限制一下 d 的范围，防止下标越界

代码：

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
ll power(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
ll dp[100005];
int main()
{
    ll n, d;
    sc("%lld%lld", &n, &d);
    if (n == 0)
    {
        pr("0\n");
        return 0;
    }
    if (n - 1 < d)
        d = n - 1;
    ll ans1 = power(2LL, n - 1) - 1;
    dp[1] = 1;
    for (int i = 1; i <= d; i++)
        dp[i] = dp[i - 1] + 1;
    for (int i = d + 1; i < n; i++)
        dp[i] = dp[i - 1] + dp[i - d - 1] + 1;
    pr("%lld\n", ans1 - dp[n - d - 1]);
}