leetcodeday110–平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

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

# [110] 平衡二叉树
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def recur(root):
            # 树为空，也是平衡二叉树
            if not root:
                return 0
            # 查看左子树
            left = recur(root.left)
            # 左子树非平衡，直接返回非平衡的结论
            if left == -1:
                return -1
            # 查看右子树
            right = recur(root.right)
            # 右子树非平衡，直接返回非平衡的结论
            if right == -1:
                return -1
            # 如果左右子树均是平衡的，那么返回它们深度的最大值并加1
            # 表示对应结点的深度
            # 如果左右子树的深度相差大于1， 那么当前结点是非平衡的
            # 总体来看，整棵树也是非平衡的
            return max(left, right) + 1 if abs(left-right) <= 1 else -1
        return recur(root) != -1
# @lc code=end        def recur(root):
            # 树为空，也是平衡二叉树
            if not root:
                return 0
            # 查看左子树
            left = recur(root.left)
            # 左子树非平衡，直接返回非平衡的结论
            if left == -1:
                return -1
            # 查看右子树
            right = recur(root.right)
            # 右子树非平衡，直接返回非平衡的结论
            if right == -1:
                return -1
            # 如果左右子树均是平衡的，那么返回它们深度的最大值并加1
            # 表示对应结点的深度
            # 如果左右子树的深度相差大于1， 那么当前结点是非平衡的
            # 总体来看，整棵树也是非平衡的
            return max(left, right) + 1 if abs(left-right) <= 1 else -1
        return recur(root) != -1