LeetCode 110. 平衡二叉树

Categories:

Tags:

题目描述
思路分析
1. 解法一：后序 DFS + 哨兵标志（推荐）
2. 解法二：自顶向下递归
相似题目

题目描述

✅ 110. 平衡二叉树

思路分析

解法一：后序 DFS + 哨兵标志（推荐）

核心思路：

判断平衡二叉树：对每个节点，左右子树高度差 ≤ 1 且左右子树也是平衡的。

朴素做法（O(n²)）：对每个节点各自求左右高度，但子树高度被重复计算。

优化：后序 DFS + 哨兵（O(n)）：用 -1 作为”已不平衡”的哨兵值，在后序遍历中同时完成高度计算和平衡判断：

若左或右子树已返回 -1（不平衡），直接向上传递 -1，提前剪枝

若 |left - right| > 1，当前子树不平衡，返回 -1

否则返回当前子树高度 max(left, right) + 1

最终根节点返回值 ≠ -1 即为平衡。一旦发现不平衡立即短路，避免冗余计算。

复杂度分析：

时间复杂度：O(n)，其中 n 为节点数，每个节点只访问一次

空间复杂度：O(h)，其中 h 为树的高度，递归栈深度

class Solution {
    public boolean isBalanced(TreeNode root) {
        // 返回值为 -1 表示子树不平衡，否则返回子树高度
        return height(root) != -1;
    }

    private int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        // 后序遍历：先递归左右子树
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);
        // 左或右子树不平衡，或当前节点高度差超过 1，直接返回 -1
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        // 返回当前节点的高度
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

func isBalanced(root *TreeNode) bool {
    // 返回高度或 -1 表示不平衡
    var height func(node *TreeNode) int
    height = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        // 后序遍历：先递归左右子树
        leftHeight := height(node.Left)
        rightHeight := height(node.Right)
        // 左或右子树不平衡，或当前节点高度差超过 1，直接返回 -1
        if leftHeight == -1 || rightHeight == -1 || abs(leftHeight-rightHeight) > 1 {
            return -1
        }
        // 返回当前节点的高度
        return max(leftHeight, rightHeight) + 1
    }
    return height(root) != -1
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

解法二：自顶向下递归

核心思路：

对每个节点，分别计算左右子树的深度，判断高度差是否超过 1，然后递归判断左右子树是否也平衡。

该方法会对同一节点重复计算深度，存在冗余，时间复杂度为 O(n²)，适合理解题意但不推荐用于生产。

复杂度分析：

时间复杂度：O(n²)，其中 n 为节点数，每个节点的深度计算会被重复调用

空间复杂度：O(h)，其中 h 为树的高度，递归栈深度

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 判断当前节点的左右子树高度差是否超过 1
        if (Math.abs(depth(root.left) - depth(root.right)) > 1) {
            return false;
        }
        // 递归判断左右子树是否也平衡
        return isBalanced(root.left) && isBalanced(root.right);
    }

    private int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    // 判断当前节点的左右子树高度差是否超过 1
    left, right := depth(root.Left), depth(root.Right)
    if abs(left-right) > 1 {
        return false
    }
    // 递归判断左右子树是否也平衡
    return isBalanced(root.Left) && isBalanced(root.Right)
}

func depth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(depth(root.Left), depth(root.Right)) + 1
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

相似题目

题目	难度	考察点
104. 二叉树的最大深度	简单	DFS 求树高
111. 二叉树的最小深度	简单	DFS 求最小深度
543. 二叉树的直径	简单	DFS 后序求最长路径
124. 二叉树中的最大路径和	困难	DFS 后序路径求和
366. 寻找二叉树的叶子节点	中等	DFS 按高度分组
1448. 统计二叉树中好节点的数目	中等	DFS 路径维护最大值

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/64786890