LeetCode 110. 平衡二叉树

Categories:

Tags:

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

题目描述

🔥 110. 平衡二叉树

思路分析

要判断一个二叉树是否是平衡的，我们可以使用递归的方法。具体思路如下：

递归计算高度：我们可以定义一个递归函数，计算每个节点的高度，并在计算过程中判断左右子树的高度差。

高度差判断：如果某个节点的左右子树高度差的绝对值大于 1，则该树不是平衡的。

返回高度：在递归过程中，返回当前节点的高度，以便父节点可以使用。

通过这种方式，我们可以在一次遍历中完成判断，避免了多次遍历带来的性能损失。

参考代码

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
}

时间复杂度：O (n)，每个节点只被访问一次。

空间复杂度：O (h)，h 是树的高度，最坏情况下为 O (n)，最优情况下为 O (log n)。

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/2023/64786890