力扣110:平衡二叉树

作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。

会一些的技术：数据分析、算法、SQL、大数据相关、python

欢迎加入社区：码上找工作

作者专栏每日更新：

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化：企业实战案例

python源码解读

程序员必备的数学知识与应用

题目描述

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

示例

示例

输入：

3
   / \
  9  20
    /  \
   15   7

输出：True

题目解读

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

1. 根节点（值为 3）:

• 左子树的高度为 1 （只有节点 9）
• 右子树的高度为 2 （包含节点 20，以及 20 的子节点 15 和 7）

2. 高度差为 |1 - 2| = 1，满足平衡树的条件。
   
3. 节点 20:

• 左子树的高度为 1 （只有节点 15）
• 右子树的高度为 1 （只有节点 7）

4. 高度差为 |1 - 1| = 0，满足平衡树的条件。
   
5. 节点 9：

• 左子树的高度为 0 （无子节点）
• 右子树的高度为 0 （无子节点）

6. 高度差为 |0 - 0| = 0，满足平衡树的条件。
   
7. 节点 15 和 节点 7：

• 作为叶子节点，左右子树高度都为 0

8. 高度差为 |0 - 0| = 0，满足平衡树的条件。
   

方法一：自顶向下的递归

解题步骤

1. 递归函数定义：定义一个辅助函数 height 来计算二叉树的最大高度。
2. 平衡判断：对每个节点，使用 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))，递归栈的深度。

方法二：自底向上的递归

解题步骤

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

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))，递归栈的深度。

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

应用示例和适用场景：

• 自顶向下递归：适用于小规模的数据或教育目的，特别是在解释和教学二叉树相关概念时，因为它简单且直接展示了递归过程和基本的树操作。
• 自底向上递归：适用于大规模数据处理，尤其在性能要求较高的系统中，如大数据处理和实时系统，其中计算效率至关重要。

欢迎关注微信公众号 数据分析螺丝钉