难度：简单
一、题目描述：
二、解题分析：
1、剑指解析
I、自顶向下
II、自底向上
2、代码实现
I、自顶向下
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# Compute the tree's height via recursion
def height(
《剑指Offer》是针对程序员面试的一本经典书籍，其中的面试题55-II主要讨论的是平衡二叉树。平衡二叉树是一种特殊的二叉树结构，它的左右两个子树的高度差不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树在数据结构中有着重要的应用，因为保持平衡可以确保操作如查找、插入和删除的时间复杂度为O(logn)。
平衡二叉树的解题通常分为两种方法：自顶向下和自底向上。
1. **自顶向下**：
自顶向下的方法通常是通过递归的方式来实现。在这个问题中，我们首先定义一个计算树高度的函数`height(root)`，对于空树返回-1，非空树则返回左子树和右子树中较高的那个再加1。然后，`isBalanced(self, root)`函数检查树是否平衡，同样通过递归，如果根节点为空，返回True，否则计算左右子树的高度差，如果差值小于2并且左右子树都是平衡的，则当前树也是平衡的。
```python
class Solution:
def height(self, root):
if not root:
return -1
return 1 + max(self.height(root.left), self.height(root.right))
def isBalanced(self, root):
if not root:
return True
return abs(self.height(root.left) - self.height(root.right)) < 2 \
and self.isBalanced(root.left) and self.isBalanced(root.right)
```
2. **自底向上**：
自底向上的方法通常通过迭代或借助辅助函数来完成。在这里，我们可以定义一个辅助函数`isBalancedHelper(root)`，返回一个元组，包含一个布尔值表示树是否平衡，以及树的高度。对于空树，返回(True, -1)。非空树时，分别检查左右子树是否平衡及它们的高度，若子树不平衡则返回(False, 0)，否则计算当前树的高度并检查是否平衡。
```python
class Solution:
def isBalancedHelper(self, root):
if not root:
return True, -1
leftIsBalanced, leftHeight = self.isBalancedHelper(root.left)
rightIsBalanced, rightHeight = self.isBalancedHelper(root.right)
if not leftIsBalanced or not rightIsBalanced:
return False, 0
return (abs(leftHeight - rightHeight) < 2, 1 + max(leftHeight, rightHeight))
def isBalanced(self):
return self.isBalancedHelper(root)[0]
```
这两种方法各有优缺点。自顶向下易于理解，但可能因为重复计算子树高度导致效率较低。自底向上避免了重复计算，但实现相对复杂，需要维护额外的信息。
在实际面试中，根据题目的要求和时间限制，选择合适的方法是非常关键的。对于平衡二叉树的题目，理解其定义，掌握这两种解题策略，并能够灵活运用，将有助于在面试中脱颖而出。同时，了解如何优化这些算法，比如使用记忆化搜索或者动态规划来减少重复计算，也会对解决问题起到很大帮助。
