【力扣】110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

• 树中的节点数在范围 [0, 5000] 内
• -104 <= Node.val <= 104

题解：

递归法：

// 时间复杂度：O(n) 这里的 n 是二叉树的节点数
// 空间复杂度：O(n) 这里的 n 是二叉树的高度
func isBalanced(root *TreeNode) bool {
	// 闭包函数，用于比较获取最大值
	max := func(a, b int) int {
		if a > b {
			return a
		}
		return b
	}
	var getHeight func(node *TreeNode) int
	getHeight = func(node *TreeNode) int {
		// 递归终止条件
		if node == nil {
			return 0
		}
		// 分别去递归左子树和右子树
		left, right := getHeight(node.Left), getHeight(node.Right)
		// 左子树或右子树为不平衡，则返回-1
		if left == -1 || right == -1 {
			return -1
		}
		// 左子树和右子树高度差大于1，则返回-1
		if left-right > 1 || right-left > 1 {
			return -1
		}
		// 返回树的高度，左子树和右子树的高度+1
		return max(left, right) + 1
	}
	return getHeight(root) != -1
}