balanced_recursive(root): """ O(N) solution """ return -1 != __get_depth(root) def __get_depth(root): """ return 0 if unbalanced else depth + 1 """ if root is None: return 0
def is_balanced(root):
return __is_balanced_recursive(root)
def __is_balanced_recursive(root):
"""
O(N) solution
"""
return -1 != __get_depth(root)
def __get_depth(root):
"""
return 0 if unbalanced else depth + 1
"""
if root is None:
return 0
left = __get_depth(root.left)
right = __get_depth(root.right)
if abs(left-right) > 1 or -1 in [left, right]:
return -1
return 1 + max(left, right)
# def is_balanced(root):
# """
# O(N^2) solution
# """
# left = max_height(root.left)
# right = max_height(root.right)
# return abs(left-right) <= 1 and is_balanced(root.left) and
# is_balanced(root.right)
# def max_height(root):
# if root is None:.
Step by step
Solved in 3 steps with 1 images
