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 everynode never differ by more than 1.
public boolean isBalanced(TreeNode root) { // Start typing your Java solution below // DO NOT write main() function if(isBalancedHelper(root)==-1){ return false; }else{ return true; } } //return -1 if the two subtrees of this node is unbalanced //return the height of this node otherwise public int isBalancedHelper(TreeNode node){ if(node==null){ return 0; }else{ int leftHeight = isBalancedHelper(node.left); int rightHeight = isBalancedHelper(node.right); if(leftHeight==-1 || rightHeight==-1){ return -1; } if(Math.abs(leftHeight-rightHeight)<=1){ return Math.max(leftHeight,rightHeight)+1; }else{ return -1; } } }
Running time is O(n) since all the nodes are visited only once.