URL

Smallest String Starting From Leaf - LeetCode

Code

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

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

let smallestFromLeaf (root: Tree) : string =
    let rec smallestFromLeaf' node acc ret =
        match node with
        | Leaf -> ret
        | Node(v, left, right) ->
            let acc' = v :: acc

            if left = Leaf && right = Leaf then
                match ret with
                | [] -> acc'
                | _ -> if acc' < ret then acc' else ret
            else
                let ret = smallestFromLeaf' left acc' ret
                smallestFromLeaf' right acc' ret

    smallestFromLeaf' root [] []
    |> List.map (fun i -> i + int 'a' |> char)
    |> System.String.Concat