LeetCode – 654. Maximum Binary Tree

題目連結: https://leetcode.com/problems/maximum-binary-tree/

func constructMaximumBinaryTree(_ nums: [Int]) -> TreeNode? {
    if nums.isEmpty { return nil }
    return helper(nums, 0, nums.count - 1)
}

func helper(_ nums: [Int], _ left: Int, _ right: Int) -> TreeNode? {
    if left <= right {
        let maxIndex = findMaxIndex(nums, left, right)
        let node = TreeNode(nums[maxIndex],
                            helper(nums, left, maxIndex - 1),
                            helper(nums, maxIndex + 1,  right))
        return node
    }
    return nil
}

func findMaxIndex(_ nums: [Int], _ start: Int, _ end: Int) -> Int {
    var maxIndex = start
    var maxVal = nums[start]
    for i in start ... end {
        if nums[i] > maxVal {
            maxVal = nums[i]
            maxIndex = i
        }
    }
    return maxIndex
}