LeetCode #110 Balanced Binary Tree

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
2
3
4
5
  3
/ \
9 20
/ \
15 7

Return true.

  • Given the following tree [1,2,2,3,3,null,null,4,4]:

    1
    2
    3
    4
    5
    6
    7
          1
    / \
    2 2
    / \
    3 3
    / \
    4 4

    Return false.

Solution

Method: Recursive

Time Complexity: O(n log n)

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def isBalanced(self, root):
if not root:
return True

return abs(self.getHeight(root.left) - self.getHeight(root.right)) < 2 and self.isBalanced(root.left) and self.isBalanced(root.right)

def getHeight(self, root):
if not root:
return 0

return 1 + max(self.getHeight(root.left), self.getHeight(root.right))

or

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution(object):
def height(self, root):
if not root:
return 0

left = self.height(root.left)
right = self.height(root.right)

if abs(left-right) > 1:
raise Exception #stop recursion and report unbalance
return 1 + max(left, right)

def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True

try:
return abs(self.height(root.left)-self.height(root.right)) <= 1
except:
return False