平衡二叉树

Question

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

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

这题可以转化为求深度，递归求左右子树的深度，每次判断左右子树是否平衡

var isBalanced = function(root) {
    if(getHeight(root)===-1)    return false
    else return true
};
var getHeight = function(root) {
    if(root==null)  return 0;
    let leftHeight = getHeight(root.left);  //左
    let rightHeight = getHeight(root.right);    //右
    if(leftHeight===-1||rightHeight===-1) return -1     //左右子树有一个不平衡
    if(Math.abs(leftHeight-rightHeight)>1){     //不平衡
        return -1
    }
    let result = leftHeight>rightHeight?1+leftHeight:1+rightHeight; //中
    return result;
};

平衡二叉树 ​

平衡二叉树