python实现leetcode之110. 平衡二叉树

解题思路

定义一个计算平衡二叉树高度的函数，不同之处是，不平衡的时候，返回-1
不平衡这个属性可以不断渗透

110. 平衡二叉树

代码

# 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 not root:
            return True
        lh = height(root.left)
        rh = height(root.right)
        return lh >= 0 and rh >=0 and lh - rh in [-1,0,1]


def height(tree):
    """
    不平衡的时候返回-1
    """
    if not tree:
        return 0
    else:
        lh = height(tree.left)
        rh = height(tree.right)
        if lh == -1 or rh == -1:
            return -1
        if lh - rh in [-1,0,1]:
            return 1+max(lh, rh)
        else:
            return -1