Convert Sorted Array to Binary Search Tree - LeetCode

Problem

1. input: 오름차순으로 정렬된 정수 배열 nums
2. output: 주어진 nums를 height-balanced 이진트리로 바꾸어 리턴
   • 1 <= nums.length <= 104
   • 104 <= nums[i] <= 104
   • nums is sorted in a strictly increasing order.

Idea

이진 트리의 루트 노드는 항상 전체 값의 중앙 값이다. 이 성질을 활용하여 중앙 값을 기준으로 좌,우를 분할 정복하면 된다 → Sol1

Solution

1. 분할 정복

   1. 주어진 배열에서 중앙 값을 루트노드로 설정
   2. 1의 루트 노드를 기준으로 배열을 나누어 각 Subtree에 대해 다시 1 반복

   /**
    * Example:
    * var ti = TreeNode(5)
    * var v = ti.`val`
    * Definition for a binary tree node.
    * class TreeNode(var `val`: Int) {
    *     var left: TreeNode? = null
    *     var right: TreeNode? = null
    * }
    */
   class Solution {
       var nums = intArrayOf()
       fun sortedArrayToBST(nums: IntArray): TreeNode? {
           this.nums = nums
           return makeTree(0, nums.size - 1)
       }
   		// 분할 정복
       fun makeTree(start: Int, end: Int): TreeNode? {
           val mid = (start + end) / 2 // 센터 = 현재 노드
           val root = TreeNode(nums[mid])
   				// 센터 기준으로 좌,우 더 쪼갤 수 있는 경우 
           if (start != mid) root.left = makeTree(start, mid - 1)
           if (end != mid) root.right = makeTree(mid + 1, end)
           return root
       }
   }
   

   시간 복잡도:

   

Point