package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

/**
 * 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 _110 {

    class Solution1 {
        //recursively get the height of each subtree of each node, compare their difference, if greater than 1, then return false
        //although this is working, but it's not efficient, since it repeatedly computes the heights of each node every time
        //Its time complexity is O(n^2).
        public boolean isBalanced(TreeNode root) {
            if (root == null) {
                return true;
            }
            if (Math.abs(getH(root.left) - getH(root.right)) > 1) {
                return false;
            } else {
                return isBalanced(root.left) && isBalanced(root.right);
            }
        }

        private int getH(TreeNode root) {
            if (root == null) {
                return 0;//base case
            }
            int leftH = getH(root.left);
            int rightH = getH(root.right);
            return Math.max(leftH, rightH) + 1;
        }
    }

    class Solution2 {

        public boolean isBalanced(TreeNode root) {
            return getH(root) != -1;
        }

        private int getH(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int leftH = getH(root.left);
            if (leftH == -1) {
                return -1;
            }
            int rightH = getH(root.right);
            if (rightH == -1) {
                return -1;
            }
            if (Math.abs(leftH - rightH) > 1) {
                return -1;
            }
            return Math.max(leftH, rightH) + 1;
        }
    }

}
@@ -82,16 +82,48 @@
 e;%0A%0A/**%0A
+ * 110. Balanced Binary Tree%0A *%0A
  * Given
@@ -174,17 +174,18 @@
 lanced.%0A
-%0A
+ *
  For thi
@@ -334,16 +334,261 @@
  than 1.
+%0A%0A Example 1:%0A Given the following tree %5B3,9,20,null,null,15,7%5D:%0A%0A    3%0A   / %5C%0A  9  20%0A  /  %5C%0A 15  7%0A%0A Return true.%0A%0A Example 2:%0A Given the following tree %5B1,2,2,3,3,null,null,4,4%5D:%0A%0A     1%0A    / %5C%0A   2   2%0A  / %5C%0A 3   3%0A/ %5C%0A4 4%0A%0A Return false.%0A 
 */%0A%0Apubl
@@ -604,24 +604,38 @@
 _110 %7B%0A%0A    
+public static 
 class Soluti
@@ -1556,16 +1556,30 @@
  %7D%0A%0A    
+public static 
 class So
@@ -2186,8 +2186,9 @@
     %7D%0A%0A%7D
+%0A

refactor 110