LeetCode 1361. Validate Binary Tree Nodes in F#

URL

Code

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

let validateBinaryTreeNodes (n: int) (leftChild: int list) (rightChild: int list) : bool =
    let rec validateBinaryTreeNodes' q visited (leftChild: int[]) (rightChild: int[]) =
        match q with
        | [] -> Set.count visited = n
        | h :: t ->
            let q', visited', ok =
                [ leftChild.[h]; rightChild.[h] ]
                |> List.filter ((<>) -1)
                |> List.fold
                    (fun (acc, visited, ok) node ->
                        if ok then
                            if Set.contains node visited then
                                acc, visited, false
                            else
                                node :: acc, Set.add node visited, true
                        else
                            acc, visited, false)
                    (t, visited, true)

            if ok then
                validateBinaryTreeNodes' q' visited' leftChild rightChild
            else
                false


    let children = Set.ofList (leftChild @ rightChild)

    let root =
        seq { 0 .. (n - 1) } |> Seq.tryFind (fun i -> not <| Set.contains i children)

    match root with
    | None -> false
    | Some(root) ->
        let visited = Set.empty |> Set.add root
        validateBinaryTreeNodes' [ root ] visited (List.toArray leftChild) (List.toArray rightChild)