110. 平衡二叉树

leecode原题

题目

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

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

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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

解题思路

思路

实现

源码

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

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

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return abs(max(maxDepth(root.Left), maxDepth(root.Right)) + 1)
}

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    if !isBalanced(root.Left) || !isBalanced(root.Right) {
        return false
    }
    if abs(maxDepth(root.Left)-maxDepth(root.Right)) > 1 {
        return false
    }
    return true
}