题目

题解

（一）
计算左子树和右子树高度，判断二者高度差是否不大于1

function IsBalanced_Solution(pRoot)
{
    if(pRoot === null) return true;
    let l = getTreeDeep(pRoot.left);
    let r = getTreeDeep(pRoot.right);
    return Math.abs(l-r)<=1 && IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);
}
function getTreeDeep(root){
    if(root===null) return 0;
    let left = getTreeDeep(root.left);
    let right = getTreeDeep(root.right);
    return 1 + (left>right?left:right);
}

• 存在问题：节点重复遍历，影响效率

（二）
改进策略：在求树的高度的同时判断是否平衡，如果不平衡返回-1，否则返回树的高度。
当左子树返回-1时，不需要再对右子树进行判断。

function IsBalanced_Solution(pRoot)
{
    return getTreeDeep(pRoot)!==-1;
}
function getTreeDeep(root){
    if(root===null) return 0;
    let left = getTreeDeep(root.left);
    if(left === -1) return -1;
    let right = getTreeDeep(root.right);
    if(right === -1) return -1;
    return Math.abs(left-right)>1 ? -1 : 1 + (left>right?left:right);
}