劍指offer-JZ39平衡二叉樹

時間限制：C/C++ 1秒，其餘語言2秒
空間限制：C/C++ 32M，其餘語言64M
熱度指數：336552
本題知識點： 樹javascript

題目描述

輸入一棵二叉樹，判斷該二叉樹是不是平衡二叉樹。java

在這裏，咱們只須要考慮其平衡性，不須要考慮其是否是排序二叉樹web

代碼

/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */
function IsBalanced_Solution(pRoot){
	//一、平衡二叉樹是一棵空樹， 
    //二、或者左右子樹的高度之差不大於1， 
    //三、子樹必須是一顆平衡二叉樹。 
    if(pRoot == null) {return true;}
    if(Math.abs(treeDepth(pRoot.left) - treeDepth(pRoot.right)) > 1) {return false;}
    return true;
}
function treeDepth(root){
    if(root === null) {return 0;}
    let leftDepth = treeDepth(root.left);
    let rightDepth = treeDepth(root.right);
    return Math.max(leftDepth, rightDepth) + 1;
}

分析：
平衡二叉樹： 任意節點的子樹的高度差都小於等於1。如B樹（多路平衡搜索樹）、AVL樹（二叉平衡搜索樹）。svg