链接：https://www.nowcoder.com/acm/contest/202/F
来源：牛客网平衡二叉树，顾名思义就是一棵“平衡”的二叉树。在这道题中，“平衡”的定义为，对于树中任意一个节点，都满足左右子树的高度差不超过 d. 空树的高度定义为0，单个节点的高度为1，其他情况下树的高度定义为根节点左右子树高度最大值 + 1. 一棵在高度上平衡的树，节点数可能不平衡，因此再定义一棵树的不平衡度为这棵树中所有节点的左右子树的节点数之差的最大值。
给定平衡的定义参数d, 你需要求出所有高度为 n 的平衡树中不平衡度的最大值。链接：来源：牛客网输入描述:
两个整数，n, d.
输出描述:
一个整数：所有高度为 n 的平衡树中不平衡度的最大值。
示例1
输入
4 1
输出
5
说明
下面这棵树在 d=1 的定义下高度是平衡的，其不平衡度为 5。
备注:
0≤ m ≤ n ≤ 60 很容易想到思路从根节点开始一边为满二叉树，另外一边为满足题目平衡条件的树的最少节点数 我和队友手推的这一题结果手算出表了但是规律找不到 难受的一批 经验严重不足 然后仔细看可以慢慢看出规律 ans表示
另外一边为满足题目平衡条件的树的最少节点数
然后仔细观察可以看到这个 ans[i] = ans[i-1] + ans[i - d - 1] + 1 附上打表代码
1 int d, sum; 2 struct node { 3 int num; 4 node *lson, *rson; 5 node () { 6 num = 1; 7 lson = rson = NULL; 8 } 9 };10 void del ( node* root ) {11 if ( !root ) return ;12 del ( root->lson );13 del ( root->rson );14 delete ( root );15 }16 int dfs ( int dep, node* root ) {17 if ( dep <= 0 ) return 0;18 root->lson = new node();19 root->num += dfs ( dep - 1, root->lson );20 sum++;21 if ( root->num - 1 > d ) {22 root->rson = new node();23 dfs ( root->num - 1 - d, root->rson );24 }25 return root->num;26 }27 int main() {28 for ( int n = 1 ; n <= 20 ; n++ ) {29 d = 1, sum = 0;30 node* root = new node();31 dfs ( n - 1 - d, root );32 printf ( "n=%d sum=%d\n", n, sum );33 del ( root );34 }35 return 0;36 } 正解代码
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include