力扣刷题（第二十三天）

灵感来源 

- 保持更新，努力学习

- python脚本学习

平衡二叉树

解题思路

解题思路

1. 递归计算高度：通过后序遍历递归计算每个节点的左右子树高度。
2. 检查平衡性：在计算高度的同时，检查每个节点的左右子树高度差是否超过 1。如果超过 1，则标记该树为不平衡。
3. 提前终止：一旦发现某个子树不平衡，立即返回结果，避免不必要的计算。

   # Definition for a binary tree node.
   # class TreeNode:
   #     def __init__(self, val=0, left=None, right=None):
   #         self.val = val
   #         self.left = left
   #         self.right = right
   class Solution:def isBalanced(self, root: Optional[TreeNode]) -> bool:def check_height(node):if node is None:return 0# 递归计算左子树高度left_height = check_height(node.left)if left_height == -1:return -1# 递归计算右子树高度right_height = check_height(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_height(root) != -1

逐行解释

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def isBalanced(self, root: Optional[TreeNode]) -> bool:# 辅助函数：检查树的高度并判断是否平衡# 如果树平衡，返回树的高度；如果不平衡，返回-1def check_height(node):# 空节点的高度为0if node is None:return 0# 递归计算左子树的高度# 如果左子树不平衡，直接返回-1left_height = check_height(node.left)if left_height == -1:return -1# 递归计算右子树的高度# 如果右子树不平衡，直接返回-1right_height = check_height(node.right)if right_height == -1:return -1# 检查当前节点的左右子树高度差是否超过1# 如果超过1，说明当前节点不平衡，返回-1if abs(left_height - right_height) > 1:return -1# 如果当前节点平衡，返回其高度（左右子树高度的最大值加1）return max(left_height, right_height) + 1# 调用辅助函数，如果返回值不为-1，则树是平衡的return check_height(root) != -1