1+ package easy ;
2+
3+ import classes .TreeNode ;
4+
5+ public class BalancedBinaryTree {
6+
7+ class Solution_1 {
8+ //recursively get the height of each subtree of each node, compare their difference, if greater than 1, then return false
9+ //although this is working, but it's not efficient, since it repeatedly computes the heights of each node every time
10+ //Its time complexity is O(n^2).
11+ public boolean isBalanced (TreeNode root ) {
12+ if (root ==null )return true ;
13+ if (Math .abs (getH (root .left ) -getH (root .right )) >1 )return false ;
14+ else return isBalanced (root .left ) &&isBalanced (root .right );
15+ }
16+
17+ private int getH (TreeNode root ) {
18+ if (root ==null )return 0 ;//base case
19+ int leftH =getH (root .left );
20+ int rightH =getH (root .right );
21+ return Math .max (leftH ,rightH )+1 ;
22+ }
23+ }
24+
25+ class Solution_2 {
26+
27+ public boolean isBalanced (TreeNode root ) {
28+ if (root ==null )
29+ return true ;
30+ return getH (root ) != -1 ;
31+ }
32+
33+ private int getH (TreeNode root ) {
34+ if (root ==null )
35+ return 0 ;
36+ int leftH =getH (root .left );
37+ if (leftH == -1 )
38+ return -1 ;
39+ int rightH =getH (root .right );
40+ if (rightH == -1 )
41+ return -1 ;
42+ if (Math .abs (leftH -rightH ) >1 )
43+ return -1 ;
44+ return Math .max (leftH ,rightH ) +1 ;
45+ }
46+ }
47+
48+ }