Leetcode: Convert Sorted Array to Binary Search Tree, 정렬된 배열을 이진 탐색 트리로 변환

문제설명

• 오름차순으로 정렬된 배열이 주어졌을 때, 이것을 높이가 균형잡힌 이진 탐색 트리로 변환하라.
• 높이가 균형잡힌(height-balanced) 이진 탐색 트리는 모든 노드의 두 서브트리의 깊이 하나 이상 차이나면 안된다.

문제풀이

• 배열이 이미 정렬되어 있으므로, 배열의 중간의 값을 선택하여 preorder 방식으로 노드를 탐색하며 노드를 추가한다.
• 배열의 중앙의 값을 선택하고 다음 중앙의 값은 서브 배열은 왼쪽과 오른쪽에서 각각 구하면 된다.

// MARK: - Answer
func sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
    return helper(arr: nums, 0, nums.count)
}
func helper(arr: [Int], _ left: Int, _ right: Int) -> TreeNode? {
    if left >= right {
        return nil
    }
    let mid = (left+right) / 2
    let root = TreeNode(arr[mid])
    root.left = helper(arr: arr, left, mid)
    root.right = helper(arr: arr, mid+1, right)
    return root
}

// MARK: - Test
var result: TreeNode!
result = sortedArrayToBST([-10,3])
print("\ncase1")
print(result.val) // 3
print(result.left!.val) // -10
print(result.right == nil) // nil

result = sortedArrayToBST([-10,3,0,5,9])
print("\ncase2")
print(result.val) // 0
print(result.left!.val) // 3
print(result.left!.left!.val) // -10
print(result.left!.right == nil) // nil

print(result.right!.val) // 9

// MARK: - Definition
public class TreeNode {
      public var val: Int
      public var left: TreeNode?
      public var right: TreeNode?
      public init() { self.val = 0; self.left = nil; self.right = nil; }
      public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
      public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
          self.val = val
          self.left = left
          self.right = right
      }
}
extension TreeNode {
    static func from(_ arr: [Int?]) -> TreeNode? {
        guard let firstElement = arr[0] else {
            return nil
        }
        let root = TreeNode(firstElement)
        var queue = [TreeNode]()
        queue.append(root)

        var index = 1
        while !queue.isEmpty && index < arr.count {

            let node = queue.removeFirst()
            if let leftVal = arr[index] {
                let left = TreeNode(leftVal)
                node.left = left
                queue.append(left)
            }
            if index+1 < arr.count, let rightVal = arr[index+1]{
                let right = TreeNode(rightVal)
                node.right = right
                queue.append(right)
            }
            index += 2
        }

        return root
    }

}