給定一個(gè)二叉樹,確定它是高度平衡的副瀑。對(duì)于這個(gè)問題,一棵高度平衡的二叉樹的定義是：一棵二叉樹中每個(gè)節(jié)點(diǎn)的兩個(gè)子樹的深度相差不會(huì)超過1想幻。
樣例
樣例 1:
輸入: tree = {1,2,3}
輸出: true
樣例解釋:
如下，是一個(gè)平衡的二叉樹弥虐。
1
/ \
2 3
樣例 2:
輸入: tree = {3,9,20,#,#,15,7}
輸出: true
樣例解釋:
如下扩灯，是一個(gè)平衡的二叉樹媚赖。
3
/ \
9 20
/ \
15 7
樣例 2:
輸入: tree = {1,#,2,3,4}
輸出: false
樣例解釋:
如下，是一個(gè)不平衡的二叉樹珠插。1的左右子樹高度差2
1
\
2
/ \
3 4
實(shí)現(xiàn)：
public class TreeNode {
public int val;
public TreeNode left, right;
public TreeNode(int val) {
this.val = val;
this.left = this.right = null;
}
}
public class Solution {
/**
* @param root: The root of binary tree.
* @return: True if this Binary tree is Balanced, or false.
*/
public boolean isBalanced(TreeNode root) {
// write your code here
if(root==null) return true;
int leftLength = maxDepath(root.left);
int rightLength = maxDepath(root.right);
return Math.abs(leftLength-rightLength)<=1 && isBalanced(root.left) && isBalanced(root.right);
}
public int maxDepath(TreeNode node){
if(node == null){
return 0;
}
int leftHeight =0;
int rightHeight = 0;
leftHeight = maxDepath(node.left);
rightHeight = maxDepath(node.right);
return leftHeight >= rightHeight? leftHeight+1 : rightHeight+1;
}
}
