平衡二叉树

《剑指offer》刷题笔记。如有更好解法，欢迎留言。

关键字：树 树的深度 平衡二叉树

题目描述：

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

思路：

• 平衡二叉树的特点是左右子树的深度相差不超过1（空树是平衡二叉树）。
• 所以先算出树的深度，判断以当前结点为根的树是否为平衡二叉树，递归判断左右子树是否为平衡二叉树。
• 完整代码

function depth(root){
    let lh,rl,h;
    if(root === null)return 0;
    lh = depth(root.left);
    rh = depth(root.right);
    if(lh >= rh){
        h = lh+1;
    }
    else{
        h = rh+1;
    }
    return h;
}
function IsBalanced_Solution(pRoot)
{
    if(pRoot === null)return true;
    let gap = depth(pRoot.left) - depth(pRoot.right);
    if(gap > 1 || gap < -1){
        return false;
    }
    return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);
}