Balanced Binary Tree

You get the root of a binary tree. Return true if the tree is height-balanced, and false if it isn't.

A tree is height-balanced when, at every node, the two subtrees differ in height by at most 1.

A tree's height is the number of nodes on its longest path down to a leaf. An empty tree has a height of 0. It counts as balanced.

The trees below are listed level by level, top to bottom and left to right. A missing child is written as nil.

Example 1:

      5
     / \
    2   8
   /   / \
  1   6   9

Input: root = [5,2,8,1,nil,6,9]
Output: true
Explanation: At 5, both subtrees have a height of 2.
At 2, the heights are 1 and 0.
A difference of 1 is allowed.
The other nodes are fine too.

Example 2:

      5
     /
    2
   /
  1

Input: root = [5,2,nil,1]
Output: false
Explanation: At the root, the left subtree has a height of 2.
The right one is empty, with a height of 0.
They differ by 2.

Example 3:

        4
       / \
      2   6
     /   / \
    1   5   8
   /         \
  0           9

Input: root = [4,2,6,1,nil,5,8,0,nil,nil,nil,nil,9]
Output: false
Explanation: At the root, both subtrees have a height of 3.
But at 2, the left subtree (1 and 0) has a height of 2.
The right subtree of 2 is empty, with a height of 0.
So the tree is not balanced at 2, even though the root is fine.

Constraints:

• 0 to 5,000 nodes.
• Each value is from -10,000 to 10,000.
• The tree is at most 800 levels deep.