描述

输入一个节点为n的二叉树，判断该二叉树是否为平衡二叉树。

在这里，我们只需要考虑平衡性，不需要考虑是不是排序二叉树

平衡二叉树具有以下性质，它是一颗空树或者它的左右两个子树的高度差绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。

前言

这道题目中平衡二叉树定义是：二叉树的每个节点的左右子树的高度差的绝对值不超过1，则二叉树是平衡二叉树，根据定义，一颗二叉树是平衡二叉树，当且仅当其所有的子树也是平衡二叉树，因此可以使用递归的方式判断二叉树是不是平衡二叉树，递归的顺序可以是自顶向下或者自底向上。

方法一：自顶向下的递归

定义函数height，用于计算二叉树中的任意一个节点p的高度:

height(p) = 0  --> p 是空节点
height(p) = max(height(p.left),height(p.right))+1  --> p 是非空节点

有了计算节点高度的函数，即可判断二叉树是否平衡，具体做法类似于二叉树的前序遍历，即对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差不超过1，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。

/**
 * 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 height = function (root) {
  if (root == null) {
    return 0;
  } else {
    return Math.max(height(root.left), height(root.right)) + 1;
  }
}
var isBalanced = function (root) {
  if(root == null) {
    return true
  } else {
    return Math.abs(height(root.left)-height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
  }
};