110 平衡二叉树

给定一个二叉树，判断它是否是 平衡二叉树

平衡二叉树的定义：是指该树所有节点的左右子树的深度相差不超过 1。

递归解法

递归三部曲，

递归的参数和返回值，

参数是根节点，返回值是最大高度或者-1（表示已经不是平衡二叉树了）

递归的终止条件

当节点为0时，返回高度0

递归的单层逻辑

//左子树的最大高度或者是-1
const leftTreeMaxHeightOrMinusOne = isBalanced(root.left)
if(leftTreeMaxHeightOrMinusOne === -1){
    return -1
}
const rightTreeMaxHeightOrMinusOne = isBalanced(root.right)
if(rightTreeMaxHeightOrMinusOne === -1) {
    return -1
}

//如果都有高度的话，看是否超过1
if(Math.abs(leleftTreeMaxHeightOrMinusOne - rightTreeMaxHeightOrMinusOne) > 1) {
    return -1
} else {
    //否则就是要返回当前树的最大高度用来和其他树比较
    return 1 + Math.max(leleftTreeMaxHeightOrMinusOne, rightTreeMaxHeightOrMinusOne)
}

那么整体的算法就如下：

var isBalanced = function (root) {
    var isBalancedPostOrder = function (root) {
        if (!root) {
            return 0
        }
        //左子树的最大高度或者是-1
        const leftTreeMaxHeightOrMinusOne = isBalancedPostOrder(root.left)
        if (leftTreeMaxHeightOrMinusOne === -1) {
            return -1
        }
        const rightTreeMaxHeightOrMinusOne = isBalancedPostOrder(root.right)
        if (rightTreeMaxHeightOrMinusOne === -1) {
            return -1
        }

        //如果都有高度的话，看是否超过1
        if (Math.abs(leftTreeMaxHeightOrMinusOne - rightTreeMaxHeightOrMinusOne) > 1) {
            return -1
        } else {
            //否则就是要返回当前树的最大高度用来和其他树比较
            return 1 + Math.max(leftTreeMaxHeightOrMinusOne, rightTreeMaxHeightOrMinusOne)
        }
    }
    return isBalancedPostOrder(root) === -1 ? false : true
};