Problem
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Examples
- Given the following tree
[3,9,20,null,null,15,7]
:
1 | 3 |
Return true.
Given the following tree
[1,2,2,3,3,null,null,4,4]
:1
2
3
4
5
6
71
/ \
2 2
/ \
3 3
/ \
4 4Return false.
Solution
Method: Recursive
Time Complexity: O(n log n)
Space Complexity:
1 | # Definition for a binary tree node. |
or
1 | # Definition for a binary tree node. |