力扣刷题TOP101: 29.BM36 判断是不是平衡二叉树

目录：

目的

思路

复杂度

记忆秘诀

python代码

目的：

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。

---

思路

什么是平衡二叉树（AVL 树）？

1. 每个节点的左子树和右子树的高度差不能超过 1。
2. 确保了在进行查找、插入和删除操作时，时间复杂度保持在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，则树是平衡的

---

* 欢迎大家探讨新思路，能够更好的理解和记忆