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

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

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

思路

  1. 递归比较左右子树的高度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var isBalanced = function (root) {
  const balancedWithMaxDepth = function (root) {
    if (!root) {
      return [true, 0]
    }
    const leftResult = balancedWithMaxDepth(root.left)
    if (!leftResult[0]) {
      return [false, 0]
    }
    const rightResult = balancedWithMaxDepth(root.right)
    if (!rightResult[0]) {
      return [false, 0]
    }
    if (Math.abs(leftResult[1] - rightResult[1]) > 1) {
      return [false, 0]
    }
    return [true, 1 + Math.max(leftResult[1], rightResult[1])]
  }
  return balancedWithMaxDepth(root)[0]
}