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.
 * 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.
 *
 * Example:
 * Given the sorted array: [-10,-3,0,5,9],
 * One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
 *
 *       0
 *      / \
 *    -3   9
 *    /   /
 *  -10  5
 */
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;
    }
  }
}

@@ -743,19 +743,19 @@
  return 
-rec
+dfs
 (num, 0,
@@ -799,19 +799,19 @@
 reeNode 
-rec
+dfs
 (int%5B%5D n
@@ -822,21 +822,22 @@
 int 
-low
+start
 , int 
-high
+end
 ) %7B%0A
@@ -850,18 +850,19 @@
 if (
-low %3E high
+start %3E end
 ) %7B%0A
@@ -910,25 +910,28 @@
 d = 
-low + (high - low
+start + (end - start
 ) / 
@@ -1001,20 +1001,22 @@
 t = 
-rec
+dfs
 (num, 
-low
+start
 , mi
@@ -1046,11 +1046,11 @@
 t = 
-rec
+dfs
 (num
@@ -1064,12 +1064,11 @@
  1, 
-high
+end
 );%0A 

refactor 108