URL

Maximum Depth of Binary Tree - LeetCode

Code

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

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

let maxDepth (root: Tree) : int =
    let rec maxDepth' q acc =
        match q with
        | [] -> acc
        | _ ->
            let acc' = q |> List.map snd |> List.max

            let q' =
                q
                |> List.fold
                    (fun acc (node, depth) ->
                        match node with
                        | Leaf -> acc
                        | Node(_, left, right) ->
                            let acc' =
                                match left with
                                | Leaf -> acc
                                | _ -> (left, depth + 1) :: acc

                            match right with
                            | Leaf -> acc'
                            | _ -> (right, depth + 1) :: acc')
                    []

            maxDepth' q' acc'

    match root with
    | Leaf -> 0
    | _ -> maxDepth' [ (root, 1) ] 0