Is it balanced?

A binary tree is height-balanced if at every node the heights of its left and right subtrees differ by at most 1. This is the AVL rule from lesson 3. An empty subtree has height −1. Return True if the tree is height-balanced and False if not.

tree [3, 9, 20, None, None, 15, 7]        ->  True
tree [1, 2, 2, 3, 3, None, None, 4, 4]    ->  False
empty tree                                ->  True

The tests write a tree as a level-order list: the values level by level, left to right, with None where a child is missing. So [3, 9, 20, None, None, 15, 7] is 3 with children 9 and 20, where 20 has children 15 and 7. An empty tree is None.

The values are not sorted: this can be any binary tree.

Limits

• Up to 131,071 nodes, at most 300 levels deep, so recursion is fine.
• Your solution should take O(n) time: work out each height once.