Leetcode : Balanced Binary Tree
Leetcode中文站：平衡二叉樹
Diffculty：Easy
關(guān)鍵字：Tree，遞歸
描述：
判斷一棵樹是否是高度平衡的二叉樹。
在本題中铲觉，高度平衡二叉樹定義為：一個(gè)二叉樹每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹的高度差的絕對值不超過 1
思路：
其實(shí)思路很簡單，使用遞歸可以很容易寫出坐榆。
1飞蛹、判斷左子樹是否平衡
2姑尺、判斷右子樹書否平衡
3清焕、判斷左右子樹高度差是否小于等于1.（當(dāng)前節(jié)點(diǎn)為root是否平衡）
要注意的點(diǎn)：
在Leetcode中文站官方解中并蝗，給出了兩種方式，自頂向下和自底向上秸妥。但這兩種方式都不可避免的進(jìn)行了多余的遞歸和多余的計(jì)算滚停。
1、判斷平衡 和 計(jì)算高度粥惧。這兩個(gè)操作都會對樹進(jìn)行遞歸键畴。如果分開操作，那么會有兩次遞歸影晓。
2、如果有某一個(gè)子樹不平衡檩禾，那么整個(gè)樹就不平衡挂签，可以直接返回結(jié)果。而不需要再去計(jì)算其他子樹了盼产。
我的思路：
就是解決上面兩點(diǎn)的問題饵婆。
1、在判斷子樹平衡的同時(shí)戏售，計(jì)算樹的高度侨核。如果平衡則返回高度草穆，不平衡返回-1。
2搓译、如果子樹不平衡直接快速失敗悲柱，避免重復(fù)計(jì)算。
運(yùn)行結(jié)果：
時(shí)間：1ms, beats 99.97%
空間：38.4MB, beats 82.19%
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
return balanceDepth(root, 1) > 0;
}
/**
* 思路：
* 1些己、一次遞歸豌鸡。在判斷子樹平衡的同時(shí)返回高度。如果不平衡則返回-1
* 2段标、快速失敗涯冠。當(dāng)判斷到某一個(gè)子樹不平衡時(shí)直接返回失敗，不再往下遞歸逼庞。
* @param node
* @param depth
* @return
*/
private int balanceDepth(TreeNode node, int depth){
if(node == null){
return depth;
}
int leftDepth = balanceDepth(node.left, depth);
if(leftDepth < 0) {
return -1;
}
int rightDepth = balanceDepth(node.right, depth);
if(rightDepth < 0){
return -1;
}
if(Math.abs(leftDepth-rightDepth) <=1){
return depth + Math.max(leftDepth, rightDepth);
}
return -1;
}
