当前位置：首页 > news >正文

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

news 2024/10/26 4:54:40

在这里插入图片描述

😀前言
在数据结构中，二叉树是一种重要的树形结构。平衡二叉树是一种特殊的二叉树，其特性是任何节点的左右子树高度差的绝对值不超过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);
}