【算法与数据结构】110、LeetCode平衡二叉树

**平衡二叉树**

平衡二叉树是一种特殊的二叉树，它的每个子树都是平衡的。也就是说，任意一个节点的左子树和右子树的高度差不超过1。

**定义**

给定一个二叉树，每个节点都有一个值，以及指向左右孩子的两个指针。我们可以用以下方法来判断一个二叉树是否是平衡的：

* 如果根节点为null，则该树是平衡的。
* 如果根节点的左子树或右子树不平衡，则该树是不平衡的。
* 否则，递归检查左右子树是否平衡。

**示例**

假设我们有一个二叉树：

3 / 
920 / 
157

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef isBalanced(root: TreeNode) -> bool:
 """
 :type root: TreeNode :rtype: bool """
 # 如果根节点为null，则该树是平衡的。
 if not root:
 return True # 计算左子树和右子树的高度差。
 left_height = get_height(root.left)
 right_height = get_height(root.right)
 # 如果左右子树的高度差超过1，则该树是不平衡的。
 if abs(left_height - right_height) >1:
 return False # 递归检查左子树和右子树是否平衡。
 return isBalanced(root.left) and isBalanced(root.right)

def get_height(root: TreeNode) -> int:
 """
 :type root: TreeNode :rtype: int """
 # 如果根节点为null，则高度为0。
 if not root:
 return0 # 递归计算左子树和右子树的高度，然后返回最大值加1。
 return max(get_height(root.left), get_height(root.right)) +1# 测试root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(isBalanced(root)) # True