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 node never differ by more than 1.
to see which companies asked this question
思路: 先写一个函数 treeDepth(root)。递归判段左右子树是否 Balanced,如果都是,他们的高度差是不是不超过 2。
- 1 class Solution(object):
- 2 def isBalanced(self, root):
- 3 """
- 4 :type root: TreeNode
- 5 :rtype: bool
- 6 """
- 7 if not root:
- 8 return True
- 9 factor = abs(self.treeDepth(root.left) - self.treeDepth(root.right))
- 10 return factor < 2 and self.isBalanced(root.left) and self.isBalanced(root.right)
- 11
- 12 def treeDepth(self, root):
- 13 if not root:
- 14 return 0
- 15
- 16 return max(self.treeDepth(root.left), self.treeDepth(root.right)) +
上面这个算法在求 treeDepth 时,每个节点都会被 visit 多次。比如算一个 node 的 father node 高度时,grand father node 高度时,cur node 的高度其实都要算一次。可以使用 Hash table 将已经 visited 过的 node 存起来。这样可以保证每个 node 只求一次高度。
- 1 d = {}
- 2 class Solution(object):
- 3 def isBalanced(self, root):
- 4 """
- 5 :type root: TreeNode
- 6 :rtype: bool
- 7 """
- 8 if not root:
- 9 return True
- 10 factor = abs(self.level(root.left) - self.level(root.right))
- 11 return factor < 2 and self.isBalanced(root.left) and self.isBalanced(root.right)
- 12
- 13 def level(self, root):
- 14 if not root:
- 15 return 0
- 16
- 17 if root in d:
- 18 return d[root]
- 19 else:
- 20 d[root] = max(self.level(root.left), self.level(root.right)) + 1
- 21 return d[root]
来源: