LeetCode 1382. Balance a Binary Search Tree in F#

URL

Balance a Binary Search Tree - LeetCode

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/challenge/202406/blance_a_binary_search_tree/main.fsx

type Tree =
    | Leaf
    | Node of int * Tree * Tree

let collectValues (root: Tree) : int list =
    let rec collectValues' node acc =
        match node with
        | Leaf -> acc
        | Node(v, left, right) ->
            let acc = collectValues' left acc
            collectValues' right (v :: acc)

    collectValues' root [] |> List.rev

let balanceBST (root: Tree) : Tree =
    let rec balanceBST' left right (v: int[]) =
        if left > right then
            Leaf
        else
            let mid = left + (right - left) / 2
            let leftTree = balanceBST' left (mid - 1) v
            let rightTree = balanceBST' (mid + 1) right v

            Node(v.[mid], leftTree, rightTree)

    let v = collectValues root |> List.toArray
    balanceBST' 0 (v.Length - 1) v