树与图简单2 种解法

#110平衡二叉树

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

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

解题主线

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

解法 1：自顶向下检查

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

时间复杂度

O(n²) 最坏，退化树会重复计算高度

空间复杂度

O(h)

110. 平衡二叉树 · 自顶向下检查

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)

110. 平衡二叉树 · 自底向上剪枝

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);
        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;
    }
}

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

边界与易错点

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

整理来源

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

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