一、问题描述

给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

二、方案二：迭代法-深度优先搜索

1、思路

• 使用深度优先搜索遍历二叉树
• 计算每个节点左右两个子树的深度
• 判断当前节点是否满足平衡二叉树

2、代码实现

func isBalanced(root *TreeNode) bool {
	if root == nil {
		return true
	}

	stack := make([]*TreeNode, 0)
	stack = append(stack, root)
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[0 : len(stack)-1]
		leftDepth := maxDepth(node.Left)
		rightDepth := maxDepth(node.Right)

		if leftDepth-rightDepth > 1 || leftDepth-rightDepth < -1 {
			return false
		}

		if node.Right != nil {
			stack = append(stack, node.Right)
		}
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
	}

	return true

}

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	leftDepth := maxDepth(root.Left)
	rightDepth := maxDepth(root.Right)

	if leftDepth < rightDepth {
		return rightDepth + 1
	} else {
		return leftDepth + 1
	}
}

3、复杂度分析

• 时间复杂度：O(n^2)，在最坏的情况下，每个节点都需要被访问多次。
• 空间复杂度：O(n)，递归栈的深度。

三、方案一：自顶向下的递归

1、思路

• 从根节点开始，递归地判断每个节点的左右子树的高度差是否不超过1。
• 对于每个节点，我们需要计算其左右子树的高度，并比较它们。
• 如果任何节点的左右子树高度差超过1，则整个树不是平衡的。

2、代码实现

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    // 计算左右子树的高度
    leftHeight := maxDepth(root.Left)
    rightHeight := maxDepth(root.Right)
    // 如果高度差大于1，则不是平衡树
    if abs(leftHeight - rightHeight) > 1 {
        return false
    }
    // 递归检查左右子树
    return isBalanced(root.Left) && isBalanced(root.Right)
}
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

3、复杂度分析

• 时间复杂度：O(n^2)，在最坏的情况下，每个节点都需要被访问多次。
• 空间复杂度：O(n)，递归栈的深度。

四、方案二：自底向上的递归

1、思路

• 从底部的叶子节点开始，向上递归判断每个节点是否平衡。
• 如果一个节点的左右子树都是平衡的，并且它们的高度差不超过1，则该节点也是平衡的。
• 如果我们提前发现任何节点不平衡，我们可以立即停止递归并返回结果。

2、代码实现

func isBalanced(root *TreeNode) bool {
    return height(root) >= 0
}
func height(root *TreeNode) int {
    if root == nil {
        return 0
    }
    // 计算左右子树的高度
    leftHeight := height(root.Left)
    rightHeight := height(root.Right)
    // 如果左右子树不平衡或高度差大于1，返回-1
    if leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1 {
        return -1
    }
    // 返回当前节点的高度
    return max(leftHeight, rightHeight) + 1
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

3、复杂度分析

• 时间复杂度：O(n)，每个节点只被访问一次。
• 空间复杂度：O(n)，递归栈的深度。

四、总结

方案	时间复杂度	空间复杂度	优点	缺点
方案一	O(n^2)	O(n)	实现简单	效率较低
方案二	O(n^2)	O(n)	实现简单	效率较低
方案三	O(n)	O(n)	效率较高	实现稍微复杂

方案三在效率上优于方案一和方案二，因为它避免了重复计算节点的高度。在实际应用中，推荐使用方案三。