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 dfs(num, 0, num.length - 1);
        }

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

@@ -82,551 +82,8 @@
 e;%0A%0A
-/**%0A * 108. Convert Sorted Array to Binary Search Tree%0A *%0A * Given an array where elements are sorted in ascending order, convert it to a height balanced 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 */%0A
 publ

refactor 108