Problem Link:
http://oj.leetcode.com/problems/balanced-binary-tree/
We use a recursive auxilar function to determine whether a sub-tree is balanced, if the tree is balanced, it also return the depth of the sub-tree.
A tree T is balanced if the following recursive conditions are satisfied:
- T's left sub-tree is balanced;
- T's right sub-tree is balanced;
- The depth of the two sub-trees never differe by more than 1.
The python code is as follows, where a recursive function check the balance in the way of top-down.
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None class Solution:
# @param root, a tree node
# @return a boolean
def isBalanced(self, root):
return self.balanced_and_depth(root)[0] def balanced_and_depth(self, node):
"""
Return [False, 0] if the sub-tree of node is not balanced,
return [True, depth] otherwise
"""
if not node:
return True, 0
lb, ld = self.balanced_and_depth(node.left)
if not lb:
return False, 0
rb, rd = self.balanced_and_depth(node.right)
if not rb:
return False, 0
if abs(ld-rd) > 1:
return False, 0
return True, 1 + max(ld,rd)