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.
public class Solution { public boolean isBalanced(TreeNode root) { return getRebalancedHeight(root)==-1?false:true; } //getHeight for each node, -1 if it is already not balanced. public int getRebalancedHeight(TreeNode root){ if(root==null){ return 0; } int leftHeight = getRebalancedHeight(root.left); int rightHeight = getRebalancedHeight(root.right); if(leftHeight==-1||rightHeight==-1||Math.abs(leftHeight-rightHeight)>1){ return -1; } return Math.max(leftHeight, rightHeight)+1; } }