110_平衡二叉树

类型：树

• 110. 平衡二叉树 💚

  https://leetcode-cn.com/problems/balanced-binary-tree/

  ❓ 判断一棵二叉树是否是高度平衡的二叉树（每个节点的左右两个子树的高度差的绝对值不超过 1）。

  💡 递归

  类似于后序遍历，对于当前节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 −1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。

  class Solution:
      def isBalanced(self, root: TreeNode) -> bool:
          def height(root: TreeNode) -> int:
              if not root:
                  return 0
              leftHeight = height(root.left)
              rightHeight = height(root.right)
              if leftHeight == -1 or rightHeight == -1 or abs(leftHeight - rightHeight) > 1:
                  return -1
              else:
                  return max(leftHeight, rightHeight) + 1
  
          return height(root) >= 0

  时间复杂度：O(n)，空间复杂度：O(n)