Given the root of a binary tree, return true if it is height balanced: at every node, the heights of the left and right subtrees differ by at most 1.
- The number of nodes is in the range 0 to 5000
- -10^4 <= Node.val <= 10^4
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The direct approach calls a height function at every node and recurses into both children, recomputing the same heights again and again, which is O(n^2) in the worst case. A post-order DFS already knows both child heights when it finishes a node, so it can check the balance condition right there. If any subtree is unbalanced we return -1, and every ancestor passes the -1 straight up, so the whole check finishes in one O(n) pass.
Algorithm
- Write
check(node)returning the height, or -1 if the subtree is unbalanced. Null returns 0. - Compute
l = check(node.left); if it is -1 return -1. Do the same forr. - If
abs(l - r) > 1, return -1. - Otherwise return
1 + max(l, r). - The tree is balanced if
check(root) != -1.
O(n)Space: O(h) recursion depth[1,2,2,3,null,null,3,4,null,null,4] has equal heights at the root but is unbalanced lower down.class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: def check(node): # height of the subtree, or -1 if it is not balanced if not node: return 0 l = check(node.left) if l == -1: return -1 r = check(node.right) if r == -1: return -1 if abs(l - r) > 1: return -1 return 1 + max(l, r)Β return check(root) != -1