LeetCode 110. 平衡二叉树

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 110. 平衡二叉树

思路分析

要判断一个二叉树是否是平衡的，我们可以使用递归的方法。

参考代码

func isBalanced(root *TreeNode) bool {
	// 返回高度或 -1 表示不平衡
	var height func(node *TreeNode) int
	height = func(node *TreeNode) int {
		if node == nil {
			return 0 // 空树高度为 0
		}

		leftHeight := height(node.Left)   // 递归计算左子树高度
		rightHeight := height(node.Right) // 递归计算右子树高度

		// 如果左子树或右子树不平衡，返回 -1
		if leftHeight == -1 || rightHeight == -1 || abs(leftHeight-rightHeight) > 1 {
			return -1
		}

		return max(leftHeight, rightHeight) + 1 // 返回当前节点的高度
	}

	return height(root) != -1 // 如果返回值不为 -1，说明树是平衡的
}

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

func isBalanced(root *TreeNode) bool {
	if root == nil {
		return true
	}
	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(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

➡️ 点击查看 Java 题解

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (Math.abs(depth(root.left) - depth(root.right)) > 1) {
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }

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

本文作者: HGNULB

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