平衡二叉树

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

思路：要想两边差最大，则左侧一定是满二叉树，右侧则是满足条件的最少节点的二叉树，所以我们首先可以预处理平衡未d的二叉树最少节点是多少，dp[i]表示满足调节树的最少节点，当深度n>d时候,dp[i]=dp[i-1]+dp[i-1-d]+1，dp[i-1]为其左侧，dp[i-1-d]为右侧，1代表根节点，
当n<=d时候，为一条链，dp[i]=dp[i-1]+1;
最后的结果为左侧满二叉树减去满足调节的最小树节点。

#include<bits/stdc++.h>
using namespace std;
int n,d;
long long dp[80];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>d;
	dp[0]=0;
	dp[1]=1;
	long long ans=1;
	for(int i=2;i<=n;i++)
	{
		if(i>d) dp[i]=dp[i-1]+dp[i-1-d]+1;
		else dp[i]=dp[i-1]+1;
		ans*=2;
	}
	long long sum=ans-1-dp[max(0,n-1-d)];
	cout<<sum<<endl;
	
}

本文地址：https://blog.csdn.net/Charles6665/article/details/107462234