算法的学习笔记—平衡二叉树(牛客JZ79)

😀前言
在数据结构中，二叉树是一种重要的树形结构。平衡二叉树是一种特殊的二叉树，其特性是任何节点的左右子树高度差的绝对值不超过1。本文将介绍如何判断一棵给定的二叉树是否为平衡二叉树，重点关注算法的时间复杂度和空间复杂度。

🏠个人主页：尘觉主页

🥰平衡二叉树

NowCoder

💝题目描述

给定一棵二叉树，判断它是否是平衡二叉树。我们只需要考虑树的平衡性，而不需要考虑树是否是排序二叉树。根据定义，一棵树是平衡的，如果它是一棵空树，或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是平衡二叉树。

例子

以下是一个平衡二叉树的例子：

对于上述树，任何节点的左右子树高度差都不超过1，因此这是一棵平衡二叉树。

💞算法思路

我们将使用深度优先搜索（DFS）的方法来判断树的平衡性。我们的主要思路如下：

1. 递归遍历树的每一个节点，计算每个节点的左子树和右子树的高度。
2. 在计算高度的过程中，判断当前节点的左右子树的高度差是否超过1。
3. 如果发现某个节点的高度差超过1，立即返回，标记树为不平衡。
4. 最后返回树是否平衡的结果。

💕代码实现

下面是 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连支持一下，创造不易您们的支持是我的动力🤞