平衡二叉树

题意：在一棵每一个节点的左右子树高度差小于d的n高度的树上，求出节点的左右子树节点差的最大值？

思路：是左子树的节点尽可能多，所以左子树为满二叉树。
右子树的节点尽可能少，所以右子树高度为n-d-1。
n高度的右子树节点个数=n-1高度的右子树节点个数+（n-d-1）高度的右子树节点个数+1。（将一棵树分为左子树，右子树，根，由于要使节点尽可能少，所以生成的左子树，右子树性质类似于该树）。
注意：当n=0和d=0时节点差为0.

代码：

#include <bits/stdc++.h>
#define inf 1000000007
using namespace std;

typedef long long ll;

ll fun(ll n,ll m)
{
    ll s=1;
    while(m)
    {
        if(m&1)
        {
            s=s*n;
        }
        n=n*n;
        m=m/2;
    }
    return s;
}

ll dp[100005];

ll dfs(ll k,ll d)
{
    if(dp[k]!=-1)
    {
        return dp[k];
    }
    if(k-d-1>0)
    {
        return dp[k]=1+dfs(k-1,d)+dfs(k-d-1,d);
    }
    else if(k-1>0)
    {
        return dp[k]=1+dfs(k-1,d);
    }
    else if(k==1)
    {
        return 1;
    }
    return 0;
}

int main()
{
    memset(dp,-1,sizeof(dp));
    ll n, d;
    scanf("%lld%lld",&n,&d);
    if(n==0||d==0)
    {
        printf("0\n");
        return 0;
    }
    ll k=n-d-1;
    ll z;
    if(k>0)
    {
    z=fun(2,n-1)-1-dfs(k,d);
    }
    else
    {
        z=fun(2,n-1)-1;
    }
    cout << z << endl;
    return 0;
}