39 平衡二叉树

题目描述

输入一棵二叉树的根节点，判断该树是不是平衡的二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

解题思路

方法一：递归+计算深度

核心思想：计算每个节点的左右子树深度，判断差值是否<=1。

方法二：后序遍历

核心思想：在遍历过程中计算深度，如果发现不平衡立即返回。

时间复杂度：O(n) 空间复杂度：O(n)

Python 实现

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


# 方法一：递归+计算深度
def is_balanced(root):
    """
    判断二叉树是否平衡（方法一）
    """
    def tree_depth(node):
        if not node:
            return 0
        return max(tree_depth(node.left), tree_depth(node.right)) + 1

    if not root:
        return True

    left_depth = tree_depth(root.left)
    right_depth = tree_depth(root.right)

    if abs(left_depth - right_depth) > 1:
        return False

    return is_balanced(root.left) and is_balanced(root.right)


# 方法二：后序遍历（优化）
def is_balanced_optimized(root):
    """
    判断二叉树是否平衡（优化版本）
    """
    def check(node):
        if not node:
            return 0, True

        left_depth, left_balanced = check(node.left)
        if not left_balanced:
            return 0, False

        right_depth, right_balanced = check(node.right)
        if not right_balanced:
            return 0, False

        if abs(left_depth - right_depth) > 1:
            return 0, False

        return max(left_depth, right_depth) + 1, True

    _, balanced = check(root)
    return balanced


# 测试代码
if __name__ == "__main__":
    # 平衡二叉树:
    #     1
    #    / \
    #   2   3
    #  / \
    # 4   5
    root1 = TreeNode(1)
    root1.left = TreeNode(2)
    root1.right = TreeNode(3)
    root1.left.left = TreeNode(4)
    root1.left.right = TreeNode(5)

    # 不平衡二叉树:
    #     1
    #    /
    #   2
    #  /
    # 3
    root2 = TreeNode(1)
    root2.left = TreeNode(2)
    root2.left.left = TreeNode(3)

    print(f"树1是否平衡: {is_balanced(root1)}")
    print(f"树2是否平衡: {is_balanced(root2)}")

# 输出:
# 树1是否平衡: True
# 树2是否平衡: False

图解

平衡二叉树示例:
        1
       / \
      2   3
     / \
    4   5

节点1: 左深度2，右深度1，差值1 ≤ 1 ✓
节点2: 左深度1，右深度1，差值0 ≤ 1 ✓
节点3: 左深度0，右深度0，差值0 ≤ 1 ✓
节点4,5: 叶节点 ✓

平衡: True

---

不平衡二叉树示例:
    1
   /
  2
 /
3

节点1: 左深度2，右深度0，差值2 > 1 ✗

不平衡: False

虽然方法一正确但效率低，每个节点的深度被重复计算。 方法二在后序遍历时计算深度，每个节点只计算一次。