1class Solution:
2 def checkBalanced(self, root):
3 return self.dfs(root)
4
5 def height(self, node, height):
6 if not node: return 0
7 if not node.left and not node.right: return 1
8 l = self.height(node.left, height)
9 r = self.height(node.right, height)
10 return max(l, r) + 1
11
12 def dfs(self, root):
13 def helper(node):
14 if not node: return True
15 if node.left:
16 if not helper(node.left): return False
17 l = self.height(node.left)
18 r = self.height(node.right)
19 if abs(l - r) > 1: return False
20 if node.right:
21 if not helper(node.right): return False
22 return True
23
24 return helper(root)