Balanced Binary Tree
- 1 min read
- LC-Easy
- Binary Tree
3 years ago
Solution
- Same as Height Balanced Binary Tree. Read that for explanation.
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def dfs(root):
if not root:
return 0, True
left_height, left_balanced = dfs(root.left)
right_height, right_balanced = dfs(root.right)
is_subtree_balanced = left_balanced and right_balanced and abs(left_height - right_height) <= 1
return 1 + max(left_height, right_height), is_subtree_balanced
return dfs(root)[1]