力扣刷题TOP101: 29.BM36 判断是不是平衡二叉树
目录：
目的
思路
复杂度
记忆秘诀
python代码
目的：
输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
思路
什么是平衡二叉树（AVL 树）？
- 每个节点的左子树和右子树的高度差不能超过 1。
- 确保了在进行查找、插入和删除操作时，时间复杂度保持在O(log n)，从而提高了数据处理的效率。
举例子：
1/ \2 3/ \
4 5
这个树是平衡二叉树：
- 对于节点
1，它的左子树高度是 2，右子树高度是 1，差值是 1，符合平衡条件。 - 对于节点
2，它的左子树高度是 1，右子树高度是 1，差值是 0，符合平衡条件。 - 对于节点
3，它的左右子树都为空，高度差是 0，符合平衡条件。
1/ 2 / 3
这个树不是平衡二叉树：对于节点 1，它的左子树高度是 2，右子树高度是 0，差值是 2，超过了 1，违反了平衡条件，说明这棵树不平衡。
代码逻辑（递归深度优先搜索（DFS））：
递归计算每个节点的子树高度：如果节点为空（
None），那么高度为0，并且认为空树是平衡的。递归计算左子树和右子树的高度：
- 先计算左子树的高度。如果左子树不平衡（返回值为
-1），直接返回-1，表示树不平衡。- 接着计算右子树的高度。如果右子树不平衡（返回值为
-1），同样返回-1。检查当前节点是否平衡：
- 对于当前节点，检查左右子树高度差的绝对值是否大于 1。如果大于 1，则表示当前节点不平衡，返回
-1。返回当前节点的高度：
- 如果当前节点平衡，则返回该节点的高度，节点高度等于左右子树高度的最大值 + 1。
最终判断树是否平衡：
- 调用递归函数
check_balance对整个树进行判断。如果树的根节点返回的值不是-1，则说明树是平衡的，返回True。否则，返回False。
示例：
1/ \2 3/ \4 5递归过程：
-
从根节点开始，检查节点 1：首先要检查左子树（节点 2）和右子树（节点 3）。
-
检查节点 2：继续检查左子树（节点 4）和右子树（节点 5）。
-
检查节点 4：节点 4 没有子节点，所以它的高度是 0。
-
检查节点 5：节点 5 也没有子节点，它的高度是 0。
-
回到节点 2：
- 左子树高度是 0（节点 4），右子树高度是 0（节点 5）。
abs(0 - 0) = 0，符合平衡条件，返回节点 2 的高度为1（max(0, 0) + 1）。
-
检查节点 3：节点 3 没有子节点，所以它的高度是 0。
-
回到根节点 1：
- 左子树高度是 1（节点 2），右子树高度是 0（节点 3）。
abs(1 - 0) = 1，符合平衡条件，返回节点 1 的高度为2（max(1, 0) + 1）。
所有节点的左右子树高度差都不超过 1，因此这棵树是平衡二叉树，最终返回 True。
复杂度
-
时间复杂度：O(n）
- 对每个节点只进行了访问一次，其中
n是树中的节点数。
- 对每个节点只进行了访问一次，其中
-
空间复杂度：O(h)
h是树的高度。递归调用栈的最大深度为树的高度。- 在最坏情况下（树是单链状），空间复杂度为 O(n)
- 在平均情况下，空间复杂度为 O(log n)，如果树比较平衡的话。
记忆秘诀
- 递归深度优先搜索计算每个节点的左右子树的高度。
- 检查高度差是否小于等于1：如果某个子树不平衡，立即返回 -1 表示不平衡，若平衡则返回该子树的高度。
python代码
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def IsBalanced_Solution(self, pRoot: TreeNode) -> bool:def check_balance(node):# 空树是平衡的，高度为 0if not node:return 0# 递归计算左右子树高度left_height = check_balance(node.left)if left_height == -1: # 左子树不平衡return -1right_height = check_balance(node.right)if right_height == -1: # 右子树不平衡return -1# 检查当前节点的平衡性if abs(left_height - right_height) > 1:return -1 # 当前节点不平衡# 返回当前节点的高度return max(left_height, right_height) + 1return check_balance(pRoot) != -1 # 如果返回值不是 -1，则树是平衡的
* 欢迎大家探讨新思路，能够更好的理解和记忆