【每日一题】7月6日平衡二叉树
平衡二叉树
https://ac.nowcoder.com/acm/problem/19775
题意
给出n,m,有一颗二叉树，两个子树之间的差不超过m，二叉树的总高度为n，然后求这颗树中左右子树之间的最大差值。解析
要求最大的差值，必定就是一颗子树上的节点尽可能地多，另一个尽可能的少，尽可能多的很容易就能解决，就是挂满就完事了，即 $2^{n-1}-1$,现在就是解决另一颗子树如何做到最少，这里我们可以通过递推，假设m为2，假设我们已经知道了$dp[1],dp[2]$现在求解$dp[3]$那么因为我们要求
就是在
的基础上再向上加一个节点，这个就是那个加一，然后我们再挂一颗子树在另一边，这另一颗子树自然是尽可能地小，最大的差值就是m,所以挂在另一边的就是
因此我们可以得出递推式
但是我们还要小心
所以最后的结果为
代码
#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
using namespace std;
const int N = 1e5 + 7;
ll dp[100];
int main(void) {
int n,m;
cin>>n>>m;
dp[1] = 1;
for (int i = 2; i <= n; ++i)
dp[i] = dp[i - 1] + dp[max(i - m - 1, 0)] + 1;
ll ans = 1ll<< n - 1;
ans -= dp[n - m - 1];
cout << ans - 1 << endl;
return 0;
}每日一题 文章被收录于专栏
写每日一题呀
比亚迪成长空间 168人发布
