LeetCode 1028. Recover a Tree From Preorder Traversal in F#

URL

https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/description/?envType=daily-question&envId=2025-02-22

Code

https://github.com/syohex/dotnet-study/blob/master/fsharp/leetcode/challenge/202502/recover_a_tree_from_preorder_traversal/main.fsx

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

let recoverFromPreorder (traversal: string) : Tree =
    let rec countDashes cs acc =
        match cs with
        | [] -> acc, []
        | h :: t -> if h = '-' then countDashes t (acc + 1) else acc, cs

    let rec readNumber cs acc =
        match cs with
        | [] -> acc, []
        | h :: t ->
            if System.Char.IsAsciiDigit(h) then
                readNumber t (acc * 10 + int h - int '0')
            else
                acc, cs

    let rec recoverFromPreorder' cs depth =
        let dashes, cs' = countDashes cs 0

        if dashes <> depth then
            Leaf, cs
        else
            let num, cs' = readNumber cs' 0
            let left, cs' = recoverFromPreorder' cs' (depth + 1)
            let right, cs' = recoverFromPreorder' cs' (depth + 1)
            Node(num, left, right), cs'

    recoverFromPreorder' (Seq.toList traversal) 0 |> fst