110. Balanced Binary Tree ⭐

Easy

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output:
 true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output:
 false

Example 3:

Input: root = []
Output:
 true

Constraints:

• The number of nodes in the tree is in the range [0, 5000].

• -104 <= Node.val <= 104

解題

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isBalanced(root *TreeNode) bool {
    if root == nil { return true }
    left := helper(root.Left)
    right := helper(root.Right)
    
    return abs(left-right) <= 1 && isBalanced(root.Left) && isBalanced(root.Right)
}

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

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

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