😀前言
在数据结构中，二叉树是一种重要的树形结构。平衡二叉树是一种特殊的二叉树，其特性是任何节点的左右子树高度差的绝对值不超过1。本文将介绍如何判断一棵给定的二叉树是否为平衡二叉树，重点关注算法的时间复杂度和空间复杂度。
🏠个人主页：尘觉主页
文章目录
- 🥰平衡二叉树
- 💝题目描述
- 例子
- 💞算法思路
- 💕代码实现
- 代码解释
- 时间和空间复杂度
- 😄总结
🥰平衡二叉树
NowCoder
💝题目描述
给定一棵二叉树，判断它是否是平衡二叉树。我们只需要考虑树的平衡性，而不需要考虑树是否是排序二叉树。根据定义，一棵树是平衡的，如果它是一棵空树，或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是平衡二叉树。
例子
以下是一个平衡二叉树的例子：
对于上述树，任何节点的左右子树高度差都不超过1，因此这是一棵平衡二叉树。
💞算法思路
我们将使用深度优先搜索（DFS）的方法来判断树的平衡性。我们的主要思路如下：
- 递归遍历树的每一个节点，计算每个节点的左子树和右子树的高度。
- 在计算高度的过程中，判断当前节点的左右子树的高度差是否超过1。
- 如果发现某个节点的高度差超过1，立即返回，标记树为不平衡。
- 最后返回树是否平衡的结果。
💕代码实现
下面是 Java 语言实现的代码：
// 定义一个布尔变量，用于跟踪树是否平衡
private boolean isBalanced = true;// 主函数，判断二叉树是否平衡
public boolean IsBalanced_Solution(TreeNode root) {// 调用辅助方法计算树的高度height(root);// 返回平衡状态return isBalanced;
}// 辅助函数，递归计算树的高度
private int height(TreeNode root) {// 如果节点为空，返回高度0// 如果树已经被标记为不平衡，则直接返回if (root == null || !isBalanced)return 0;// 递归计算左子树的高度int left = height(root.left);// 递归计算右子树的高度int right = height(root.right);// 检查当前节点的左右子树高度差是否超过1// 如果高度差超过1，则将isBalanced标记为falseif (Math.abs(left - right) > 1)isBalanced = false;// 返回当前节点的高度，当前节点的高度为左右子树高度的最大值加1return 1 + Math.max(left, right);
}代码解释
TreeNode类定义了二叉树的节点结构。IsBalanced_Solution方法是主要的入口函数，调用height方法计算树的高度并检查平衡性。height方法递归地计算每个节点的高度，并在计算过程中检查左右子树的高度差。
时间和空间复杂度
- 时间复杂度：O(n)，其中 n 是节点数。每个节点只被访问一次。
- 空间复杂度：O(1)，不需要额外的空间用于存储状态，但递归调用栈的空间复杂度为 O(h)，其中 h 是树的高度。在最坏情况下（例如一条链），h 可能等于 n。
😄总结
通过递归方法，我们可以高效地判断一棵二叉树是否为平衡二叉树。这种方法不仅直观，而且在时间和空间复杂度上都表现良好。通过以上示例代码，开发者可以轻松实现并验证二叉树的平衡性
😁热门专栏推荐
想学习vue的可以看看这个
java基础合集
数据库合集
redis合集
nginx合集
linux合集
手写机制
微服务组件
spring_尘觉
springMVC
mybits
等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持
🤔欢迎大家加入我的社区 尘觉社区
文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞
