力扣110:平衡二叉树

作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
LeetCode解锁1000题: 打怪升级之旅
python数据分析可视化：企业实战案例
python源码解读
程序员必备的数学知识与应用

题目描述

给定一个二叉树，判断它是否是高度平衡的。对于这个问题，一个高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例

输入：

输出：True

题目解读

要判断这棵树是否为高度平衡的，根据定义，一个高度平衡的二叉树要求每个节点的左右两个子树的高度差的绝对值不超过 1。我们可以通过计算每个节点的左右子树的高度来进行判断。

根节点（值为 3）:
- 左子树的高度为 1 （只有节点 9）
- 右子树的高度为 2 （包含节点 20，以及 20 的子节点 15 和 7）
高度差为 |1 - 2| = 1，满足平衡树的条件。
节点 20:
- 左子树的高度为 1 （只有节点 15）
- 右子树的高度为 1 （只有节点 7）
高度差为 |1 - 1| = 0，满足平衡树的条件。
节点 9：
- 左子树的高度为 0 （无子节点）
- 右子树的高度为 0 （无子节点）
高度差为 |0 - 0| = 0，满足平衡树的条件。
节点 15 和节点 7：
- 作为叶子节点，左右子树高度都为 0
高度差为 |0 - 0| = 0，满足平衡树的条件。

方法一：自顶向下的递归

解题步骤

递归函数定义：定义一个辅助函数 height 来计算二叉树的最大高度。
平衡判断：对每个节点，使用 height 函数计算左右子树的高度，检查高度差是否不超过 1，并递归地对所有子节点进行同样的操作。

Python 示例

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isBalanced(root):
    def height(node):
        """ 计算树的高度 """
        if not node:
            return 0
        return max(height(node.left), height(node.right)) + 1
    
    if not root:
        return True
    left_height = height(root.left)
    right_height = height(root.right)
    return abs(left_height - right_height) <= 1 and isBalanced(root.left) and isBalanced(root.right)

# 示例调用
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(isBalanced(root))  # 输出: True

算法分析

时间复杂度：(O(n^2))，在最坏的情况下，对于每个节点都需要重新计算高度。
空间复杂度：(O(n))，递归栈的深度。

方法二：自底向上的递归

解题步骤

优化递归：计算节点高度的同时，检查子树是否平衡。
早停机制：一旦发现子树不平衡，立即停止计算并返回。

Python 示例

def isBalanced(root):
    def check(node):
        if not node:
            return 0
        left = check(node.left)
        if left == -1:
            return -1
        right = check(node.right)
        if right == -1:
            return -1
        if abs(left - right) > 1:
            return -1
        return max(left, right) + 1
    
    return check(root) != -1

# 示例调用
print(isBalanced(root))  # 输出: True

算法分析

时间复杂度：(O(n))，每个节点访问一次。
空间复杂度：(O(n))，递归栈的深度。

以下是自顶向下递归和自底向上递归两种方法进行平衡二叉树检查的优劣势对比表格，专注于这两种常见且实用的解决方案：

方法	优点	缺点
自顶向下递归	- 易于理解和实现 - 教学有益，直观展示递归检查过程	- 效率较低：重复计算高度 - 时间复杂度为 (O(n^2))，对于大树效率低
自底向上递归	- 高效，避免重复计算 - 每个节点只访问一次，时间复杂度 (O(n))	- 实现相对复杂 - 需要理解返回值的同时进行两种检查（高度和平衡性）