noodleProblems/
Balanced Binary Tree
#131

Balanced Binary Tree

AlgorithmeasyTreeDepth First SearchBinary Tree

Given the root of a binary tree, return true if it is **height-balanced**.

A binary tree is height-balanced when, for *every* node, the heights of its left and right subtrees differ by at most one. The check is local at every node, not just at the root.

The tree is given as a level-order array where null marks a missing child: [3, 9, 20, null, null, 15, 7] is root 3 with children 9 and 20, and 20 has children 15 and 7.

Example cases

  • balanced
    in root = [3,9,20,null,null,15,7]9315207
    out true
    Every node's subtree heights differ by at most 1.
  • skewed
    in root = [1,2,2,3,3,null,null,4,4]4342312
    out false
    The left subtree is depth 3 while the right is depth 1 — the root is unbalanced.
  • empty
    in root = []null
    out true

Constraints

  • The number of nodes in the tree is in the range [0, 5000].
  • -10^4 <= Node.val <= 10^4
Saved
root =
[3,9,20,null,null,15,7]