【每日一题】 7-6 平衡二叉树
题意：
给定平衡二叉树的高度，并且给定平衡因子，求这颗树中所有结点的左右子树的节点数之差
做法：
一开始看错了题意，以为是根节点的左右子树之差，然后直接左子树满二叉树，右子树一条链，WA到自闭，然后发现是所有结点的左右子树，所以考虑构造出一条链高度为 n 并且他的另一个子树满足与他的长度差为 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]);
} 
腾讯公司福利 1156人发布
