Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
判定一个二叉树是否是平衡二叉树。
即二叉树所有子树深度差别都不超过1。
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
int l = Depth(root.left);
int r = Depth(root.right);
if( l<0 || r<0 || Math.abs(l-r)>1) return false;
else return true;
}
public int Depth(TreeNode node){
if(node == null) return 0;
int l = 0, r = 0;
if(node.left != null) l = Depth(node.left);
if(node.right != null) r = Depth(node.right);
if( l<0 || r<0 || Math.abs(l-r)>1) return -1; //即该节点root下的子树已经不平衡了
else return Math.max(l,r) + 1; //如果左右子树是平衡的，那么返回深度＋1
}
}
