BinaryTree_Leetcode_108. Convert Sorted Array to Binary Search Tree [swift]

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/?envType=study-plan-v2&envId=top-100-liked

 

접근 방법

        // even, odd 파악. odd인 경우, 중간의 값을 root. 이를 기준으로 좌우로 array를 나누어 lhs, rhs로 나눔
        // 반복하여 tree구성.
        // even인 경우 중간의 두 개중 큰걸 쓰자. 123456789
        //              5
        //         3        8
        //      2    4    7     9
        //    1          6

코드

/**
 * Definition for a binary tree node.
 * 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
 *     }
 * }
 */
class Solution {
    func sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
        var sol: TreeNode?
        

        func makeNode(input: [Int], parent: inout TreeNode?) {
            guard !input.isEmpty else { return }
            
            let shouldBeRootIndex = Int(round(Double(input.endIndex - 1) / 2))
            var current: TreeNode? = TreeNode(input[shouldBeRootIndex])
            if parent == nil {
                parent = current
            } else if parent?.left == nil {
                parent?.left = current
            } else {
                parent?.right = current
            }

            let lhs = Array(input[0..<shouldBeRootIndex])
            let rhsCount = max(input.count - 1 - lhs.count, 0)
            let rhs = Array(input.suffix(rhsCount))
            
            makeNode(input: lhs, parent: &current)
            makeNode(input: rhs, parent: &current)
        }

        makeNode(input: nums, parent: &sol)

        return sol
    }
}

 

간단 해설

문제의 Tree구성에 대한 조건은 height-balanced였다. 그래서, 중간값을 root로 사용하며, input array를 계속 쪼개나가면 된다고 생각했다.

let shouldBeRootIndex = Int(round(Double(input.endIndex - 1) / 2))

해당 변수를 통하여, 중간의 index를 구한다. input.count가 odd인경우 정 가운데 값이 나오지만, even인 경우, 두 가운데 값 중 큰 것을 사용한다.

var current: TreeNode? = TreeNode(input[shouldBeRootIndex])

if parent == nil {

parent = current

} else if parent?.left == nil {

parent?.left = current

} else {

parent?.right = current

}

parent == nil인 경우는 초기값에 해당한다. 처음 parent는 nil로 시작한다.