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 /** 2  * Definition for binary tree 3  * public class TreeNode { 4  *     int val; 5  *     TreeNode left; 6  *     TreeNode right; 7  *     TreeNode(int x) { val = x; } 8  * } 9  */10 public class Solution {11     public boolean isBalanced(TreeNode root){12        boolean isBalanced = true;13         if(root != null){14             if(heightOfTree(root.left) > heightOfTree(root.right) + 1 || 15                  heightOfTree(root.left) < heightOfTree(root.right) - 1)16                  isBalanced = false;17             else18                  isBalanced = isBalanced(root.left) && isBalanced(root.right);19         }20         return isBalanced;21     }22     23     public int heightOfTree(TreeNode root){24         int height = 0;25         if(root != null)26             height = 1 + Math.max(heightOfTree(root.left), heightOfTree(root.right));27         return height;28     }    29 }