The problem
A binary tree is height-balanced if, at every node, the heights of its left and right subtrees differ by at most one. Given the root, return whether the tree is height-balanced.
Examples
01
- Input
root = [3, 9, 20, null, null, 15, 7]
- Output
true
02
- Input
root = [1, 2, 2, 3, 3, null, null, 4, 4]
- Output
false
03
- Input
root = []
- Output
true
Constraints
- 0 ≤ number of nodes ≤ 5000
- −10⁴ ≤ Node.val ≤ 10⁴
The idea
Checking each node by computing its subtrees’ heights from scratch repeats work: n nodes, each measuring up to n below it.
Instead compute every height once, bottom-up, and let a node report −1 — “unbalanced” — if either child did, or if its children’s heights differ by more than one. The −1 rises straight to the root, so one pass answers the question.
- Time
- O(n)
- Space
- O(h)
Solution · every language run against every case
class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: def height(node): # the height, or -1 as soon as anything below is unbalanced if not node: return 0 left, right = height(node.left), height(node.right) if left < 0 or right < 0 or abs(left - right) > 1: return -1 return 1 + max(left, right) return height(root) >= 0