平衡二叉树------递推

根据题意，找出左右子树最大差值，这个最大值一定是通过这颗树的根节点的左右子树的差值得到的，对于左子树，我们可以令他为满二叉树，这样的节点数最多，假设深度为n，那么左子树为满二叉树的节点数 ,对于右子树，如果差值要越大，那么节点数尽可能小，我们只要求出高度差为不超过d且深度为n-d-1的平衡树的最少节点数即可，接下来上图：
假设n=8 d=2；如何构造最小的二叉树，一步一步递推，
以下全部是左右子树差值不超过d=2的平衡二叉树的最少节点画法

深度为1

深度为2

深度为3

深度为4

深度为5

深度为6

深度为7

深度为8

上面全部图都是差值为d=2的限制
我们可以发现，对于最少节点的平衡树，深度为X的最少节点平衡树的根节点的左子树的数量是深度为X-d-1的最少节点平衡树的节点数，这里我们可以得出了递推式
令 为深度是x的最少节点平衡树的节点数，得出



所以我们可以对于给出的深度n，差值d，左子树为满二叉树节点数为 ,右子树是最少节点平衡二叉树， ,两者之差就是最大值了。

#include <cctype>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define pll pair<long long, long long>
#define P pair<int, int>
#define PP pair<P, P>
#define eps 1e-10
#define PI 3.1415926535898
#define It set<node>::iterator
using namespace std;
const int maxn=1e3+10;
ll f[maxn];
int main() {
    ll n,m;
    cin>>n>>m;
    ll sum=1;
    if (n==0) {
        cout<<0<<endl;
        return 0;
    } else if (n==1) {
        cout<<0<<endl;
        return 0;
    }
    for (int i=1; i<n; i++) {
        sum*=2;
    }
    sum-=1;
    for (int i=1; i<=m; i++) f[i]=f[i-1]+1;
    for (int i=m+1; i<=n; i++) {
        f[i]+=f[i-1];
        f[i]+=f[i-m-1]+1;
    }
    cout<<sum-f[n-m-1]<<endl;
    return 0;
}