您现在的位置是:首页 > 正文

判断一棵树是否为平衡二叉树

2024-01-30 23:20:57阅读 0

平衡二叉树即为树中任意节点的左右两子树高度差不超过1

struct TreeNode
{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int a) :val(a), left(NULL), right(NULL) {};
};

struct rType {
	bool isBalanced;
	int height;
	rType(bool is, int h) :isBalanced(is), height(h) {};
};
rType isbalance(TreeNode * p)
{
	if (p == NULL)return rType(true, 0);
	rType left = isbalance(p->left);
	rType right = isbalance(p->right);

	int height = max(left.height, right.height) + 1;//The current tree height is the maximum of left and right subtree height plus 1
	bool isbBalanced = left.isBalanced&&right.isBalanced && (abs(left.height - right.height) < 2);
	return rType(isbBalanced, height);
}

bool isBalancedTree(TreeNode * p)//main()
{
	return isbalance(p).isBalanced;
}

网站文章

  • C++ QT CRC16校验 函数封装 最新发布

    CRC16 C++ QT QString的校验方式

    2024-01-30 23:20:28
  • Typescript学习(二):编译选项

    Typescript学习(二):编译选项

    这个strict相关标志位的一个总开关, 设置为true会启用全部compilerOptions.strict开头的选项和其他相关的选项, 如compilerOptions.strictNullChe...

    2024-01-30 23:20:21
  • 【项目原理】DRM驱动概念、组成、框架、源码分析

    【项目原理】DRM驱动概念、组成、框架、源码分析

    Linux 中的驱动和驱动是两种不同的图形驱动方式,它们之间有一些区别。DRM驱动:总之,一句话,DRM是Linux目前主流的图形显示框架,相比FB架构,DRM更能适应当前日益更新的显示硬件。

    2024-01-30 23:20:14
  • LInux——五种IO模型

    LInux——五种IO模型

    Linux中的IO简述IO主要分为以下的三种:内存IO网络IO磁盘IO通常我们所说的IO是后两者,Linux中无法直接操作IO设备,必须通过系统调用请求kernal来协助完成IO的动作,内存会为每一个...

    2024-01-30 23:20:06
  • PageHelper 分页查询「实现篇」

    两种情况分两种情况:查出来为 PageQueryRespDTO查出来直接是 Model查出来为 PageQueryRespDTOpublic PageInfo<PageQueryRespDTO> qu...

    2024-01-30 23:19:36
  • 洛谷题目目录 热门推荐

    #1 新手村 关卡1-1 洛谷的第一个任务 超级玛丽游戏(洛谷-P1000):点击这里 A+B Problem(洛谷-P1001):点击这里 小玉买文具(洛谷-P1421):点击这里 小鱼的游泳时间(...

    2024-01-30 23:19:28
  • mysql数据丢失_MySQL是如何保证数据的完整性

    mysql数据丢失_MySQL是如何保证数据的完整性

    本文内容主要介绍了MySQL是如何保证数据的完整性,帮助大家更好的理解和学习MySQL,感兴趣的朋友可以了解下!!!数据的一致性和完整性对于在线业务的重要性不言而喻,如何保证数据不丢呢?今天我们就探讨下关于数据的完整性和强一致性,MySQL做了哪些改进。一. MySQL的二阶段提交 在Oracle和MySQL这种关系型数据库中,讲究日志先行策略(Write-Ahead Logging),只要...

    2024-01-30 23:19:20
  • python软件下载安装百度网盘-python网盘下载

    python软件下载安装百度网盘-python网盘下载

    广告关闭2017年12月,云+社区对外发布,从最开始的技术博客到现在拥有多个社区产品。未来,我们一起乘风破浪,创造无限可能。pip install tencentcloud-sdk-python 注意...

    2024-01-30 23:18:50
  • php.ini开启jd库,.user.ini

    .user.ini究竟是个神秘东东?我们看看官方怎么说:http://php.net/manual/zh/configuration.file.per-user.php自 PHP 5.3.0 起,PH...

    2024-01-30 23:18:43
  • git@github.com: Permission denied (publickey) 热门推荐

    git@github.com: Permission denied (publickey) 热门推荐

    今天在使用命令ssh -T git@github.com测试公钥是否添加成功时,提示:git@github.com: Permission denied (publickey)解决方法方法一:使用默认名字 重新生成密钥对,不指定名字,使用默认名字方法二:使用ssh-agent代理管理git私钥 如果使用的是自己定义的名字 添加本地私钥:ssh-add ~/.ssh/自己定义的名字...

    2024-01-30 23:18:37