Balanced Binary Tree Validation

A binary tree is height-balanced if, for every node in the tree, the heights of its left and right subtrees differ by no more than 1. (The height of an empty subtree is defined as -1, or equivalently you can define an empty subtree as height 0 and a single-node tree as height 1 — just be consistent.)

Given the root of a binary tree, determine whether it is height-balanced.

Example 1

Input: [3, 9, 20, null, null, 15, 7]

      3
     / \
    9  20
       / \
      15  7

Output: true

Example 2

Input: [1, 2, 2, 3, 3, null, null, 4, 4]

          1
         / \
        2   2
       / \
      3   3
     / \
    4   4

Output: false — the subtree rooted at the first 2 has left height 2 and right height 0, a difference of 2.

Example 3

Input: [] → Output: true (an empty tree is trivially balanced).

Constraints

• The number of nodes is in the range [0, 5000].
• -10^4 <= Node.val <= 10^4.