110. Balanced Binary Tree
难度: 简单
刷题内容
原题连接
- https://leetcode.com/problems/balanced-binary-tree
内容描述
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.
Example 1:
Given the following tree [3,9,20,null,null,15,7]:
3
/ \
9 20
/ \
15 7
Return true.
Example 2:
Given the following tree [1,2,2,3,3,null,null,4,4]:
1
/ \
2 2
/ \
3 3
/ \
4 4
Return false.
解题方案
思路 1
递归,判断左右子树最大高度差不超过1且左右子树均为平衡树
class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def height(node):
if not node:
return 0
return 1 + max(height(node.left), height(node.right))
if not root:
return True
return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)
