- 标签:树、深度优先搜索、递归
- 难度:简单
给定一个二叉树,判断它是否是高度平衡的二叉树。即左右两个子树的高度差的绝对值不超过 1 。
递归遍历二叉树。先递归遍历左右子树,判断左右子树是否平衡,再判断以当前节点为根节点的左右子树是否平衡。
如果遍历的子树是平衡的,则返回它的高度,否则返回 -1。
只要出现不平衡的子树,则该二叉树一定不是平衡二叉树。
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def height(root: TreeNode) -> int:
if root == None:
return False
leftHeight = height(root.left)
rightHeight = height(root.right)
if leftHeight == -1 or rightHeight == -1 or abs(leftHeight-rightHeight) > 1:
return -1
else:
return max(leftHeight, rightHeight)+1
return height(root) >= 0