Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
# 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 """ if root == None: return True left = self.depth(root.left) right = self.depth(root.right) return abs(left-right) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right) def depth(self, root): if root == None: return 0 return max(self.depth(root.left), self.depth(root.right)) + 1
1.定义一个depth函数,用于计算从当前位置起的depth
2.从根节点开始计算其左子树和右子树分别的depth,iterative,两者差距小于1,并且其左子树和右子树都balance,则其为balance