LeetCode 110. 平衡二叉树

约 5 分钟
文章信息 18 个分类 4 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 50-100 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 拼多多 亚马逊 虾皮
标签
深度优先搜索 树 二叉树 二叉树经典题
目录

题目描述

✅ 110. 平衡二叉树

image-20230305213112788

image-20230305213108413

题意分析

判断一棵二叉树是否「高度平衡」。这里的平衡定义必须读准：每个节点的左右子树高度差都不超过 1，而不是只看根节点。一棵树完全可能根节点两侧高度相等，但某个更深的节点已经失衡——只查根是过不了的，这也是本题最常见的理解偏差。

题目里其实藏着两个子问题：如何求一棵子树的高度，以及如何把「每个节点都要检查」这件事组织得不重复劳动。前者是熟悉的递归，后者才是本题真正想考的。

数据范围上节点数不超过 5000，边界情况包括：空树按定义视为平衡；单节点树平衡；链状树（每个节点只有一个孩子）在深度达到 2 以上时必然失衡。

解法：后序 DFS 返回高度或失衡标记

核心思路

问题的关键不是求根节点两侧的高度，而是保证每个节点都平衡。若从上往下逐节点调用独立的高度函数，同一棵子树会被祖先反复遍历，链状树最坏达到 $O(n^2)$；后序 DFS 能在检查父节点前先拿到左右子树的高度，因此每个节点只需处理一次。

定义 height(node)：子树平衡时返回真实高度，子树内任一节点失衡时返回 -1。真实高度非负，所以 -1 可以安全地同时表示“失衡”。得到左右结果后，只要一侧为 -1 或高度差大于 1，就继续向上返回 -1；否则返回 max(left, right) + 1。

正确性来自后序递归的不变量：处理当前节点时，左右返回值已经准确描述各自子树。两侧都平衡且高度差不超过 1，当前子树才平衡；否则它必然失衡。失衡标记一路传到根，最终只需判断根的返回值是否为 -1。

解题步骤

  • 空节点高度记为 0。
  • 递归计算左子树；若返回 -1，整棵当前子树已经失衡，立即短路。
  • 递归计算右子树，并做同样的短路判断。
  • 若左右高度差大于 1，返回 -1；否则返回较大高度加 1。
  • 主函数检查 height(root) != -1。例如某节点得到左右高度 3 和 1 时，会返回 -1，其祖先无需再计算高度差。

代码实现

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }

    private int height(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftHeight = height(node.left);
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = height(node.right);
        if (rightHeight == -1) {
            return -1;
        }

        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

func isBalanced(root *TreeNode) bool {
    return heightOrUnbalanced(root) != -1
}

func heightOrUnbalanced(node *TreeNode) int {
    if node == nil {
        return 0
    }

    leftHeight := heightOrUnbalanced(node.Left)
    if leftHeight == -1 {
        return -1
    }
    rightHeight := heightOrUnbalanced(node.Right)
    if rightHeight == -1 {
        return -1
    }

    if absInt(leftHeight-rightHeight) > 1 {
        return -1
    }
    return maxInt(leftHeight, rightHeight) + 1
}

func absInt(num int) int {
    if num < 0 {
        return -num
    }
    return num
}

func maxInt(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

  • 时间复杂度：$O(n)$。每个节点至多访问一次，高度由两个子结果直接合成。
  • 空间复杂度：$O(h)$。h 为树高，递归栈在平衡树上为 $O(\log n)$，链状树最坏为 $O(n)$。

关键点总结

  • 状态必须同时覆盖“子树高度”和“子树是否平衡”，-1 哨兵恰好把两者合并。
  • 后序遍历符合依赖方向：父节点的判断依赖孩子的高度与平衡状态。
  • 收到 -1 要立即向上传递，不能再把它当作合法高度参与计算。
  • 面试若追问替代写法，可以返回 (高度, 是否平衡)；含义更显式，但 Java 需要额外结构。

易错点总结

  • 只比较根节点：根两侧可能等高，但更深层节点已经失衡。
  • 将条件写成 >= 1：高度差恰好为 1 仍然平衡，应判断 > 1。
  • 忘记绝对值：只检查 left - right > 1 会漏掉右侧更高的树。
  • 空节点返回 -1：会把空树误判为失衡；空节点的高度应为 0。
  • 子树返回 -1 后仍执行 max + 1：哨兵可能被覆盖，导致失衡信息丢失。

相似题目

题目 难度 考察点
104. 二叉树的最大深度 简单 只求高度不做判定，是本题递归返回值的子问题
111. 二叉树的最小深度 简单 单侧为空时不能直接取最小，叶子定义需要特判
559. N 叉树的最大深度 简单 把左右两叉的高度递推推广为遍历孩子列表取最大
剑指 Offer 55 - I. 二叉树的深度 简单 与 104 同源，练习自底向上合成高度的基本功
剑指 Offer 55 - II. 平衡二叉树 简单 与本题同题，可直接复用哨兵短路模板
面试题 04.04. 检查平衡性 简单 换一种叙述考察同一判定，重点仍是逐节点检查