URL

https://leetcode.com/problems/unique-binary-search-trees-ii/description/

Code

https://github.com/syohex/dotnet-study/blob/master/fsharp/leetcode/problems/0095/main.fsx

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

let generateTrees (n: int) : Tree list =
    let rec combinations a b acc =
        match a with
        | [] -> List.rev acc
        | h :: t ->
            let acc' = b |> List.fold (fun acc e -> (h, e) :: acc) acc
            combinations t b acc'

    let rec generateTrees' left right =
        if left > right then
            [ Leaf ]
        else
            seq { left..right }
            |> Seq.fold
                (fun acc n ->
                    let leftTrees = generateTrees' left (n - 1)
                    let rightTrees = generateTrees' (n + 1) right

                    combinations leftTrees rightTrees []
                    |> List.fold (fun acc (leftTree, rightTree) -> (Node(n, leftTree, rightTree) :: acc)) acc)
                []

    generateTrees' 1 n |> List.rev