每日一题力扣110 平衡二叉树

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

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

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

把递归就当作三个节点，左 根 右。这层递归里要做的事情就是找到最大高度，找最大高度就是左子树算完最大高度，右子树也算完最大高度，然后+1即可。所以就是右max（height（左），height（右））+1的存在。

得到了该根节点的最大高度之后，还要左右子树的最大高度相减必须小于等于1才是平衡二叉树；不仅当前根节点要满足这个条件，这棵树中的所有根节点都必须满足平衡二叉树，所以就有最后一行两个and的存在

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        #递归要关心的事：
        #1.终止条件：肯定是节点为空
        #2.返回值是什么，是节点的最大高度
        #3.本级递归要做什么：要找到子树的最大高度
        def height(root: TreeNode) -> int:
            if not root:
                return 0
            return max(height(root.left), height(root.right)) + 1#返回的是最大的高度

        if not root:#如果没有节点，肯定就是平衡二叉树
            return True
        return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)#左右子树都需要是平衡二叉树，并且root要左右子树相减小于等于1