【每日一题】平衡二叉树

这个题坑点在于和我们一般的BBT不一样。我们说平衡因子一般是要<d。但是这里是<=d。这点要注意。

然后就来分析一下题目。

• 首先，特判两种情况n=1||n==0输出0就行了

• 考虑一般情况，画个图发现，如果f[n]表示平衡因子不超过d的最小结点数量。那么f[n]=1+f[n-1]+f[n-1-d].前提是n>=d+1
  那么n<d+1呢？很简单，一条链就ok

  #include<bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  ll f[70];
  int main()
  {
  ll n,d;
  cin>>n>>d;
  f[0]=0;
  if(n==0||n==1) return cout<<0<<endl,0;
  for(int i=1;i<=d+1;i++ ) f[i]=i;//一条链就是满足条件的最少数量形态
  for(int i=d+2;i<=n;i++) f[i]=f[i-1]+f[i-1-d]+1;//考虑合并左右子树
  
  cout<<(1ll<<(n-1))-1-f[n-1-d]<<endl;
  return 0;
  }