Balanced Binary Tree
EasyTrees
Given the root of a binary tree, return True if the tree is *height-balanced* and False otherwise.
A binary tree is height-balanced when, at every node, the heights of its left and right subtrees differ by at most 1. The height of a subtree is the number of nodes on its longest downward path, so an empty subtree has height 0. An empty tree is balanced.
Trees are written in level order: values are listed level by level, left to right, and null marks a missing child (trailing nulls are omitted).
Example 1
- Input:
- root = [1,2,3,4,null,null,null,5]
- Output:
- False
- Explanation
- Node 2 has a left subtree of height 2, running down through 4 to 5, and no right subtree at all. A difference of 2 breaks the rule, even though node 4 on its own is fine.
Example 2
- Input:
- root = [1,2,3,4,5,null,6,7]
- Output:
- True
- Explanation
- The longest branch 1 → 2 → 4 → 7 is only one level deeper than the root's right side, and at every node the two subtree heights differ by at most 1.
Example 3
- Input:
- root = [1,2,3,4,null,null,5,6,null,null,7]
- Output:
- False
- Explanation
- At the root both subtrees have height 3, so the root looks fine. But node 2 has a left subtree of height 2 and an empty right subtree, so the tree is not balanced.
Constraints
- The number of nodes is in the range
[0, 5000] -10^4 <= Node.val <= 10^4- The tree height is at most
500