023 · Balanced Binary Tree

Problem

给定一棵二叉树的根节点 root。

请判断这棵二叉树是否是高度平衡的。

一棵二叉树是高度平衡的，意思是：对树中的每一个节点来说，它的左子树和右子树的高度差都不能超过 1。

注意，这个要求不只是检查根节点。

树里面的每一个节点都要满足这个条件：

• 左子树高度和右子树高度相差 0 或 1，可以接受
• 如果某个节点的左右子树高度差大于 1，整棵树就不是平衡的

例如，下面这棵树是平衡的：

      3
     / \
    9   20
       /  \
      15   7

根节点左右两边的高度差没有超过 1，下面的节点也都满足要求。

下面这棵树不是平衡的：

        1
       / \
      2   2
     / \
    3   3
   / \
  4   4

因为左边某些节点下面太深，导致左右子树高度差超过了 1。

Examples

示例 1

Input:  root = [3,9,20,null,null,15,7]
Output: true

解释：每个节点的左右子树高度差都不超过 1，所以这棵树是平衡的。

示例 2

Input:  root = [1,2,2,3,3,null,null,4,4]
Output: false

解释：树的左侧更深，存在节点的左右子树高度差超过 1，所以不是平衡二叉树。

示例 3

Input:  root = []
Output: true

解释：空树可以看作是高度平衡的。

Constraints

• 树中节点的数量范围是 \([0, 5000]\)
• \(-10^4 \leq\) Node.val \(\leq 10^4\)

Link

• Original Problem

---

→ Solution