package cn.foolishbird.arithmetic.leetcode.low.ConvertSortedArrayToBinarySearchTree;

import cn.foolishbird.arithmetic.leetcode.TreeNode;
import org.junit.Test;

/**
 * @author Eric
 * @version 1.0
 * @date 2020-11-04
 */
public class Solution {

    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }

    public TreeNode dfs(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }

        int middle = (start + end + 1) / 2;
        TreeNode root = new TreeNode(nums[middle]);
        root.left = dfs(nums, start, middle - 1);
        root.right = dfs(nums, middle + 1, end);
        return root;
    }

    @Test
    public void test() {
        int[] nums = {-10, -3, 0, 5, 9};
        sortedArrayToBST(nums);
    }
}