如何判断二叉树是否平衡

1. 概述

树结构是计算机科学中最核心的数据结构之一。我们之所以特别关注平衡二叉树，是因为它具备极佳的性能特性——查询、插入、删除等操作的时间复杂度可以稳定在 O(log n)。

本文将带你实现一个高效的算法，用于判断一棵二叉树是否为平衡树。内容不搞花里胡哨，直奔主题，适合有经验的开发者快速回顾或踩坑参考。

2. 基本定义

先统一几个关键概念，避免理解偏差：

二叉树（Binary Tree）：每个节点最多有两个子节点的树结构
树的高度（Height）：从根节点到最深叶子节点的最长路径长度（即最大深度）
平衡树（Balanced Tree）：对于任意子树，其左子树和右子树的高度差不超过 1

✅ 正确理解：这里的“平衡”指的是高度平衡（height-balanced），不是左右节点数量相等。

举个例子，下面这棵二叉树就是平衡的：

图中三条绿色边标出了从根到最深叶子的路径，数字表示层级。可以看出左右子树高度差为 1，满足平衡条件。

3. 数据结构设计

先定义树节点：

public class Tree {
    private int value;
    private Tree left;
    private Tree right;

    public Tree(int value, Tree left, Tree right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    // 标准 getter 方法
    public int value() { return value; }
    public Tree left() { return left; }
    public Tree right() { return right; }
}

⚠️ 注意：为简洁起见，这里假设节点值为整数。left 和 right 为 null 时表示当前节点是叶子节点。

接下来定义递归过程中的返回结果封装类：

private class Result {
    private boolean isBalanced;
    private int height;

    private Result(boolean isBalanced, int height) {
        this.isBalanced = isBalanced;
        this.height = height;
    }
}

这个 Result 类很关键，它同时携带两个信息：

当前子树是否平衡
当前子树的高度

这样可以避免重复遍历，提升效率。

4. 算法实现

核心思路：对每个节点进行递归检查，利用后序遍历（左右根）自底向上收集信息。

我们采用深度优先搜索（DFS），在每层递归中：

先处理左右子树
获取子树的平衡状态和高度
判断当前节点是否满足平衡条件

递归逻辑

private Result isBalancedRecursive(Tree tree, int depth) {
    if (tree == null) {
        return new Result(true, -1); // 空树视为平衡，高度为 -1
    }

    // 递归处理左右子树
    Result leftSubtreeResult = isBalancedRecursive(tree.left(), depth + 1);
    Result rightSubtreeResult = isBalancedRecursive(tree.right(), depth + 1);

    // 判断当前节点是否平衡
    boolean isBalanced = Math.abs(leftSubtreeResult.height - rightSubtreeResult.height) <= 1;
    boolean subtreesAreBalanced = leftSubtreeResult.isBalanced && rightSubtreeResult.isBalanced;
    int height = Math.max(leftSubtreeResult.height, rightSubtreeResult.height) + 1;

    return new Result(isBalanced && subtreesAreBalanced, height);
}

关键点解析

空节点处理：返回 isBalanced = true，height = -1，这样叶子节点高度为 0，逻辑更统一
高度差判断：Math.abs(leftHeight - rightHeight) <= 1
短路逻辑：只有当左右子树都平衡，且高度差 ≤1 时，当前树才算平衡

外部调用接口

为了简化使用，提供一个外观方法（facade）：

public boolean isBalanced(Tree tree) {
    return isBalancedRecursive(tree, -1).isBalanced;
}

这样调用者无需关心递归细节和初始深度。

5. 总结

本文实现了一个简单粗暴但高效的判断二叉树是否平衡的算法：

✅ 时间复杂度：O(n)，每个节点访问一次
✅ 空间复杂度：O(h)，h 为树高，递归栈深度
✅ 关键技巧：一次递归返回多个信息，避免重复计算

该实现适用于大多数面试和实际场景。如果你在写递归时经常“卡住”，建议多模仿这种“封装返回值”的模式，能显著提升代码清晰度和正确性。

示例代码已托管至 GitHub：https://github.com/john-doe/tutorials/tree/master/algorithms/balanced-tree

Persistence

REST

Security