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; //即該節(jié)點root下的子樹已經不平衡了
else return Math.max(l,r) + 1; //如果左右子樹是平衡的与斤，那么返回深度＋1
}
}
