110. Balanced Binary Tree
Easy LeetCodeGiven a binary tree, determine if it is height-balanced.
Example 1
Input: root = [3,9,20,null,null,15,7]
Output: true
Example 2
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Example 3
Input: root = []
Output: true
Constraints
- The number of nodes in the tree is in the range [0, 5000]
- -104 <= Node.val <= 104
How to solve the problem
Code
- Recursion
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def get_height(node) -> int:
if node is None:
return 0
left_height = get_height(node.left) # determine left height
if left_height == -1:
return -1
right_height = get_height(node.right)
if right_height == -1 or abs(left_height - right_height) > 1: # determine right height
return -1
return max(left_height, right_height) + 1 # max depth
return get_height(root) != -1 # if the value returned from get_height is not -1, it is a balance tree
Complexity
- Time complexity: O(n), n == number of nodes
- Space complexity: O(n)
Comments
No comments yet. Be the first to comment!