110. 平衡二叉树.py

# 给定一个二叉树，判断它是否是高度平衡的二叉树。
# 本题中，一棵高度平衡二叉树定义为：
# 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。
#
# 示例 1：
# 输入：root = [3,9,20,null,null,15,7]
# 输出：true
#
# 示例 2：
# 输入：root = [1,2,2,3,3,null,null,4,4]
# 输出：false
#
# 示例 3：
# 输入：root = []
# 输出：true
#
# 提示：
# 树中的节点数在范围 [0, 5000] 内
# -104 <= Node.val <= 104

# 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 dfs(node: TreeNode) -> int:
            if node is None:
                return 0
            l, r = dfs(node.left), dfs(node.right)
            if l == -1 or r == -1 or abs(l - r) > 1:
                return -1
            return max(l, r) + 1

        return dfs(root) != -1