平衡二叉树_牛客博客

题目描述

平衡二叉树，顾名思义就是一棵“平衡”的二叉树。在这道题中，“平衡”的定义为，对于树中任意一个节点，都满足左右子树的高度差不超过 d. 空树的高度定义为0，单个节点的高度为1，其他情况下树的高度定义为根节点左右子树高度最大值 + 1. 一棵在高度上平衡的树，节点数可能不平衡，因此再定义一棵树的不平衡度为这棵树中所有节点的左右子树的节点数之差的最大值。
给定平衡的定义参数d, 你需要求出所有高度为 n 的平衡树中不平衡度的最大值。

输入描述:

两个整数，n, d.

输出描述:

一个整数：所有高度为 n 的平衡树中不平衡度的最大值。

题解

对于这道题，我们最后要求的是高度为n的平衡树中所有节点的左右子树的节点数之差的最大值。我们考虑怎么样能够让它们差值最大。我们只需要让左子树的结点尽可能多而右子树的节点尽可能少就可以了。
左子树的结点尽可能多，那我们就让左子树为满二叉树，在此种情况下满足左右子树的高度差不超过d，符合平衡的要求。对于右子树，我们要做的就是构造一个满足左右子树的高度差不超过d且节点数最小的树。这个问题就可以把问题规模缩小，利用dp进行求解。用 $f[i]$ 表示深度为 $i$ 的满足以上条件的树的节点，那么 $f[i]=f[i-1]+f[i-d-1]+1$ ,然后我们逐步递推就好了。

代码

#include<bits/stdc++.h>
 using namespace std;
#define ll long long 
 int n,d;
 ll f[100];
 int main(){
     scanf("%d%d",&n,&d);
     if(n==0||n==1){
         printf("0\n");
     }
     else{
         f[0]=0,f[1]=1;
         ll sum=1;
         for(int i=2;i<=n;++i){
             sum=sum*2;
             if(i>d)f[i]=f[i-1]+f[i-1-d]+1;
             else f[i]=f[i-1]+1;
         }
         printf("%lld\n",sum-1-f[max(n-d-1,0)]);
     }
     return 0;
 }