Balanced Binary Tree

easy

Given a binary tree, determine if it is height-balanced — that is, a tree in which the left and right subtrees of every node differ in height by no more than 1.

Test Cases

Copy an input into the main harness and Run to verify

Input

root = [3,9,20,null,null,15,7]

Expected Output

true

Input

root = [1,2,2,3,3,null,null,4,4]

Expected Output

false

Input

root = []

Expected Output

true

Constraints

The number of nodes in the tree is in the range [0, 5000].
-10^4 <= Node.val <= 10^4

Hints

Hint 1 — click to reveal

Computing the height separately at every node repeats a lot of work.

Hint 2 — click to reveal

Let one traversal return the height *and* signal imbalance — a sentinel like -1 works well.

Java Compiler