【LeetCode OJ】Balanced Binary Tree

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:

  1. T's left sub-tree is balanced;
  2. T's right sub-tree is balanced;
  3. 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)
上一篇:js中的深拷贝和浅拷贝


下一篇:4. Traffic monitoring tools (流量监控工具 10个)