Leetcode: Balanced Binary Tree

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;
 }
}
FacebookTwitterGoogle+Share

Leave a Reply

Your email address will not be published. Required fields are marked *