题目名称

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

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

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

示例

[1,2,2,3,null,null,3,4,null,null,4]
[]
[3,9,20,null,null,15,7]
[1,2,2,3,3,null,null,4,4]
false
true
true
false

题解

递归解决，计算子树高度，-1表示子树已经不平衡了

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
  var isBalanced = function(root) {
  if(!root) return true
  return getDeep(root) !== -1
};

function getDeep(root) {
  if(!root) return 0
  let left = getDeep(root.left)
  let right = getDeep(root.right)
  if(left < 0 || right < 0) return -1
  if(Math.abs(left - right) <= 1) {
    return Math.max(left, right) + 1
  }
  return -1
}