欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

平衡二叉树

程序员文章站 2022-07-28 18:45:15
1.平衡二叉树定义:如果一棵树不为空,其任意节点的左子树高度与右子树高度之差不超过1,那么满足这样条件的树就是平衡二叉树 2.平衡二叉树节点定义: 这里平衡二叉树节点定义使用了模版,这样就可以任意自定义节点,using BINNODE = tagNode则是为节点类型起一个别名, using ......

平衡二叉树,顾名思义就是一棵“平衡”的二叉树。在这道题中,“平衡”的定义为,对于树中任意一个节点,都满足左右子树的高度差不超过 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

相关标签: 牛客刷题