package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

/**
 * 108. Convert Sorted Array to Binary Search Tree
 *
 * Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
 */
public class _108 {

  public static class Solution1 {
    public TreeNode sortedArrayToBST(int[] num) {
      return rec(num, 0, num.length - 1);
    }

    public TreeNode rec(int[] num, int low, int high) {
      if (low > high) {
        return null;
      }
      int mid = low + (high - low) / 2;
      TreeNode root = new TreeNode(num[mid]);
      root.left = rec(num, low, mid - 1);
      root.right = rec(num, mid + 1, high);
      return root;
    }
  }
}

@@ -237,16 +237,400 @@
 ed BST.%0A
+ * For this problem, a height-balanced binary tree is defined as a binary tree in which%0A * the depth of the two subtrees of every node never differ by more than 1.%0A *%0A * Example:%0A * Given the sorted array: %5B-10,-3,0,5,9%5D,%0A * One possible answer is: %5B0,-3,9,-10,null,5%5D, which represents the following height balanced BST:%0A *%0A *       0%0A *      / %5C%0A *    -3   9%0A *    /   /%0A *  -10  5%0A
  */%0Apubl

refactor 108