【每日一题】平衡二叉树
平衡二叉树
https://ac.nowcoder.com/acm/problem/19775
这个题坑点在于和我们一般的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; }
左边刷题右边 chat 效果很好