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

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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]
}