树与图简单2 种解法

#110平衡二叉树

判断每个节点左右子树高度差是否都不超过一。

#二叉树#深度优先搜索#后序遍历

原题

给定一个二叉树，判断它是否是平衡二叉树

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

树中的节点数在范围 [0, 5000] 内
-10⁴ <= Node.val <= 10⁴

查看原题

解题主线

自底向上可同时返回高度和失败信号，发现失衡后立即剪枝。

解法 1：自顶向下检查

对每个节点计算两侧高度，并递归验证左右子树。

时间复杂度： O(n²) 最坏，退化树会重复计算高度
空间复杂度： O(h)

JAVA

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public boolean isBalanced(TreeNode root) {
        // 空树满足平衡定义，也是递归终止边界。
        if (root == null) return true;
        // 当前节点高度差合格后，仍需递归保证两棵子树内部都平衡。
        return Math.abs(height(root.left) - height(root.right)) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }

    private int height(TreeNode node) {
        if (node == null) return 0;
        // 高度由左右子树较大值加一得到；该写法会在祖先处重复计算。
        return Math.max(height(node.left), height(node.right)) + 1;
    }
}

解法 2：自底向上剪枝

后序计算高度，以 -1 表示当前子树已经失衡。

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

JAVA

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public boolean isBalanced(TreeNode root) {
        // 非负返回值表示整棵树平衡，并同时携带真实高度。
        return height(root) >= 0;
    }

    private int height(TreeNode node) {
        if (node == null) return 0;
        int left = height(node.left);
        // -1 是失衡哨兵，发现后无需继续遍历另一侧。
        if (left < 0) return -1;
        int right = height(node.right);
        if (right < 0 || Math.abs(left - right) > 1) return -1;
        // 仅当左右子树都平衡时，当前层才返回实际高度。
        return Math.max(left, right) + 1;
    }
}

边界与易错点

只检查根节点高度差不够，所有子树都必须平衡。
朴素自顶向下会重复计算高度。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/tree/Q110_isBalanced.java
leetcode/src/main/java/tree/Q110_tree_isBalanced.java