[LeetCode] Convert Sorted Array to Binary Search Tree (Kotlin)

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree

Convert Sorted Array to Binary Search Tree - LeetCode

오름차순 배열이 주어졌을 때, 높이 균형 트리(height-balanced)를 구현하는 문제이다.
분할과 정복을 통해 구현할 수 있었다.

중복 처리가 어렵다면 visit 배열을 만들어서 구현해도 무방하다.

fun sortedArrayToBST(nums: IntArray): TreeNode? {
    val mid = nums.size / 2
    val root = TreeNode(nums[mid])
    root.left = makeTree(nums, 0, mid - 1)
    root.right = makeTree(nums, mid + 1, nums.lastIndex)
    return root
}

fun makeTree(nums: IntArray, min: Int, max: Int): TreeNode? {
    if (min > max) {
        return null
    }
    val mid = (min + max) / 2
    val newNode = TreeNode(nums[mid])

    newNode.left = makeTree(nums, min, mid - 1)
    newNode.right = makeTree(nums, mid + 1, max)

    return newNode
}