A binary tree is height-balanced if, for every node, the heights of its left and right
subtrees differ by at most 1. Given the root, return True if the tree is height-balanced.
An empty tree is balanced.
Examples
3
/ \
9 20
/ \
15 7
Input: root = build_tree([3, 9, 20, None, None, 15, 7])
Output: True
1
/ \
2 2
/ \
3 3
/ \
4 4
Input: root = build_tree([1, 2, 2, 3, 3, None, None, 4, 4])
Output: False
Explanation: at the root, the left subtree has height 3 and the right has height 1.
Constraints
0 <= number of nodes <= 2000- Target complexity: O(n) time.
Goals
- Compute subtree heights bottom-up
- Propagate a failure signal without recomputing heights
- Avoid the O(n^2) naive approach