LeetCode 110. 平衡二叉树

题目

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

例：
输入：root = [3,9,20,null,null,15,7]
输出：true

方法：递归

判断每个节点左右子树的高度的差值是否大于 1，那么应使用后序遍历
求节点的高度部分：

• 首先判断节点是否为空
• 计算该节点的左右子树的高度
• 若左子树或右子树的高度为 -1，那么表示之前已经得知该二叉树不平衡，继续返回 -1 即可
• 若左右子树的高度差大于 1，此时以中间节点为根节点的二叉树不为平衡二叉树，那么二叉树不为平衡二叉树，返回 -1；若左右子树的高度差小于等于 1，那么返回该中间节点的高度
  判断是否平衡部分：
• 若高度为 -1，则表示不为平衡二叉树
• 若高度为其他值，则表示为平衡二叉树

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isBalanced(self, root):
        if self.height(root) != -1:
            return True
        else:
            return False

    def height(self, node):
        if node == None:
            return 0
        left = self.height(node.left)
        right = self.height(node.right)
        if left == -1 or right == -1:
            return -1
        if abs(left - right) > 1:
            return -1
        else:
            return 1 + max(left, right)