LeetCode 987. Vertical Order Traversal of a Binary Tree in F#

URL

leetcode.com/problems/vertical-order-traver..

Code

github.com/syohex/dotnet-study/blob/master/..

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

let verticalTraversal (root: Tree) : int list list =
    let rec verticalTraversal' node row col acc =
        match node with
        | Leaf -> acc
        | Node (v, left, right) ->
            let acc' =
                match Map.tryFind col acc with
                | None -> Map.add col (Map.add row [ v ] Map.empty) acc
                | Some (m) ->
                    match Map.tryFind row m with
                    | None -> Map.add col (Map.add row [ v ] m) acc
                    | Some (vals) -> Map.add col (Map.add row ((v :: vals) |> List.sort) m) acc

            let acc'' =
                verticalTraversal' left (row + 1) (col - 1) acc'

            verticalTraversal' right (row + 1) (col + 1) acc''

    let rec f cols m acc =
        match cols with
        | [] -> acc |> List.rev
        | h :: t ->
            let cols = Map.find h m

            let rows =
                Map.keys cols
                |> Seq.sort
                |> Seq.fold
                    (fun a i ->
                        let vals = Map.find i cols
                        a @ vals)
                    []

            f t m (rows :: acc)

    let m = verticalTraversal' root 0 0 Map.empty
    let cols = m |> Map.keys |> Seq.sort |> Seq.toList
    f cols m []