杰森影像网站建设/深圳网络推广收费标准

题目描述

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

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

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

解题思路

• 分治法
• 左子树平衡，右子树平衡
• 左右子树深度不超过一
• 符合条件返回深度，否则返回-1（-1代表非平衡）

代码实现

func isBalanced(root *TreeNode) bool {if maxDepth(root) == -1 {return false}return true
}func maxDepth(root *TreeNode) int {if root == nil {return 0}leftDepth := maxDepth(root.Left)rightDepth := maxDepth(root.Right)if leftDepth == -1 || rightDepth == -1 ||leftDepth-rightDepth > 1 || rightDepth-leftDepth > 1 {return -1}if leftDepth > rightDepth {return leftDepth+1}return rightDepth+1
}