110_balanced_binary_tree

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

代码参考：

package main

func main() {
    // debug in LeetCode Code editor
}

// 递归从下往上判断各子树的平衡结果
func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }

    lDepth := depth(root.Left)
    rDepth := depth(root.Right)
    if abs(lDepth-rDepth) > 1 { // 平衡条件
        return false
    }

    return isBalanced(root.Left) && isBalanced(root.Right)
}

// 某子树的深度
func depth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    lDepth := depth(root.Left) + 1
    rDepth := depth(root.Right) + 1 // 加节点本身的深度

    if lDepth > rDepth {
        return lDepth
    }
    return rDepth
}

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