# My python solution with horrible run time

• ``````    #my solution
class Solution:
# @param {TreeNode} root
# @return {boolean}
def isBalanced(self, root):
if root==None:
return True
if not self.isBalanced(root.left) or not self.isBalanced(root.right):
return False
if root.left==None:
return root.right==None or root.right.left==None==root.right.right
if root.right==None:
return root.left.left==None==root.left.right
stack=[]
stack.append((root.left,0,1))
lh=0
while stack:
node,lev,h=stack.pop()
if node!=None and not lev:
stack.append((node,1,h))
stack.append((node.left,0,h+1))
elif node!=None and not lev-1:
stack.append((node,2,h))
stack.append((node.right,0,h+1))
if node!=None:
lh=max(lh,h)
stack.append((root.right,0,1))
rh=0
while stack:
node,lev,h=stack.pop()
if node!=None and not lev:
stack.append((node,1,h))
stack.append((node.left,0,h+1))
elif node!=None and not lev-1:
stack.append((node,2,h))
stack.append((node.right,0,h+1))
if node!=None:
rh=max(rh,h)
return abs(rh-lh)<2``````

• You can use BFS or DFS to solve this problem which is quite straight forward:

``````# BFS
def isBalanced(self, root):
queue = []
queue.append(root)
while queue:
curr = queue.pop(0)
if curr:
if abs(self.height(curr.left) - self.height(curr.right)) > 1:
return False
if curr.left:
queue.append(curr.left)
if curr.right:
queue.append(curr.right)
return True

# DFS
def isBalanced(self, root):
stack = []
stack.append(root)
while stack:
curr = stack.pop()
if curr:
if abs(self.height(curr.left) - self.height(curr.right)) > 1:
return False
if curr.right:
stack.append(curr.right)
if curr.left:
stack.append(curr.left)
return True

def height(self, root):
if not root:
return 0
return max(self.height(root.left), self.height(root.right)) + 1
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.