LeetCode 110. 平衡二叉树

约 5 分钟
文章信息 20 个分类 3 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 50-100 腾讯 字节 阿里 微软 亚马逊 美团 拼多多 小米 百度 快手 滴滴 虾皮 招行 猿辅导
标签
深度优先搜索 树 二叉树

题目描述

✅ 110. 平衡二叉树

image-20260928195059126

image-20260928195059128

题意分析

判断整棵二叉树是否满足高度平衡：对于每一个节点，它的左右子树高度差都不能超过 1。这里比较的是子树高度，不是左右两边的节点数量。

条件要求对所有节点成立。即使根节点两边等高，某棵子树内部也可能已经失衡，因此不能只比较根节点；空树满足平衡条件。

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

核心思路

[!blue]

判断一个节点是否平衡，需要先知道左右子树的高度，还要知道这两棵子树内部是否平衡。因此适合后序遍历：先处理孩子，再根据它们返回的信息判断当前节点。

用一个整数同时携带两种信息：非负数表示“这棵子树平衡，数值是它的高度”，-1 表示“这棵子树中已经存在失衡节点”。空子树返回 0，所以 -1 不会与任何正常高度冲突。

先递归左子树。如果它返回 -1，当前子树无论右边怎样都不可能满足“所有节点平衡”，可以立即返回 -1。右子树同理。只有两边都平衡，才比较它们的高度差；超过 1 就在当前节点判定失衡，否则返回 max(leftHeight, rightHeight) + 1。

这样每个节点在求高度时顺便完成平衡检查，父节点直接复用结果，不必为了检查每个节点而反复遍历其后代。失衡标记会一直传到根，主函数只需判断根的返回值是否为 -1。

解题步骤

  1. 当前节点为空时返回 0，表示空子树的高度。
  2. 递归求左子树结果。如果为 -1，立即返回失衡标记。
  3. 递归求右子树结果，同样先检查是否已经失衡。
  4. 两边都给出正常高度后，若高度差的绝对值大于 1，返回 -1；否则返回较大高度加 1。
  5. 主函数检查整个树的结果，不等于 -1 就返回 true。

代码实现

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)$。

关键点总结

[!green]

  • 当前节点的判断同时依赖孩子的高度和孩子是否平衡，不能丢掉任一信息。
  • 后序返回高度，使整棵树只需遍历一次，不重复计算子树高度。
  • -1 是失衡信号，收到后直接向上传递，不能参与正常高度的合并。

易错点总结

[!yellow]

  • 只比较根节点两侧高度，会遗漏子树内部已经发生的失衡。
  • 用左右节点数之差代替高度差，检查的不是题目要求的条件。
  • 高度差恰好为 1 仍然平衡，判定条件应为 > 1，而不是 >= 1。
  • 只检查 leftHeight - rightHeight > 1 会漏掉右边更高的情况，需要取绝对值。
  • 空节点应返回 0；返回 -1 会错误地把空子树判为失衡。
  • 收到 -1 后仍做 max + 1，可能把失衡标记转换成非负高度，丢失错误信息。

相似题目

题目 难度 关联与区别
104. 二叉树的最大深度 简单 后序求高度是基础，本题同时把子树是否失衡的信息向上传递。
543. 二叉树的直径 简单 同样用左右子树高度在当前节点计算附加结果，原题求最长路径长度。
124. 二叉树中的最大路径和 困难 后序返回子树高度并在根处合并信息；本题额外验证两侧高度差，该题舍弃负贡献后合并最大路径和。
687. 最长同值路径 中等 后序返回子树高度并在根处合并信息；本题额外验证两侧高度差，该题仅连接值相同的向下链。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/64786890
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！