The idea is to count the depth of left subtree and right subtree and compare them. But we should also know whether the subtrees are balanced. In Python, the function can return multiple variables (as a tuple). We can use this feature.
# 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 isBalanced(self, root): """ :type root: TreeNode :rtype: bool """ def check(r): if r == None: return True, 0 balanced1, h1 = check(r.left) balanced2, h2 = check(r.right) balanced = balanced1 and balanced2 and abs(h1-h2)<=1 h = max(h1, h2) + 1 return balanced, h balanced, h = check(root) return balanced