110. Balanced Binary Tree
You receive the root of a binary tree. Report whether the tree is height-balanced, returning true or false.
Height-balanced means the condition holds at every node, not just the root: the height of a node's left subtree and the height of its right subtree never differ by more than one. Height here counts nodes along the longest downward path, so an empty subtree has height 0 and a leaf has height 1.
An empty tree is balanced. Watch out for trees whose two halves are individually balanced yet sit at heights two apart — those must be rejected.
Example 1:
Input: root = [3, 9, 20, null, null, 15, 7]
Output: true
Explanation: At the root, the left subtree has height 1 and the right height 2 — a difference of 1, which is allowed — and every deeper node is trivially balanced.
Example 2:
Input: root = [1, 2, 2, 3, 3, null, null, 4, 4]
Output: false
Explanation: The root's left subtree reaches height 3 while its right subtree has height 1: a gap of 2 breaks the rule.
Constraints:
- 0 ≤ number of nodes ≤ 2000
- -10⁴ ≤ node value ≤ 10⁴
Hints:
You will need subtree heights. Write the classic recursive height: an empty subtree is 0, otherwise 1 plus the taller child's height.
Checking `|height(left) - height(right)| <= 1` at the root is not enough — the same test has to pass at every node, so recurse the balance check into both children too.
Calling a separate height() inside a recursive balance check recomputes heights over and over. Do both jobs in one postorder pass: have the recursion return the subtree height, or a sentinel like -1 the moment any subtree turns out unbalanced, and short-circuit upward.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [3, 9, 20, null, null, 15, 7]
Expected output: true