[LeetCode]110. 平衡二叉树

110. 平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

解法1

在求解二叉树最大高度的过程中就能判断出是否为平衡二叉树.

class Solution:
    def isBalanced(self, root):
        self.balanced = True
        def height(root):
            if not root:
                return 0
            heightR = height(root.right)
            heightL = height(root.left)
            if abs(heightR - heightL) > 1:
                self.balanced = False
            return max(heightR, heightL)+1
        height(root)
        return self.balanced

解法2

和解法1思路相似, 用-1来标记非平衡, 递归求解左子树和右子树.

class Solution:
    def isBalanced(self, root):
        def balanced(root):
            if not root:
                return 0
            left = balanced(root.left)
            right = balanced(root.right)
            if left == -1 or right == -1 or abs(left - right) > 1:
                return -1
            return 1 + max(left, right)
        return balanced(root) != -1