URL

leetcode.com/problems/lowest-common-ancesto..

Code

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

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

let lowestCommonAncestor (root: Tree) (p: int) (q: int) : int =
    let rec collectAncestors' node num acc =
        match node with
        | Leaf -> None
        | Node (v, left, right) ->
            let acc' = v :: acc

            if v = num then
                Some(acc' |> List.rev)
            else
                match collectAncestors' left num acc' with
                | None -> collectAncestors' right num acc'
                | ret -> ret

    let rec lowestCommonAncestor' ps qs prev =
        match ps, qs with
        | [], []
        | [], _
        | _, [] -> prev
        | h1 :: t1, h2 :: t2 ->
            if h1 = h2 then
                lowestCommonAncestor' t1 t2 h1
            else
                prev


    let pAncestors = (collectAncestors' root p []).Value
    let qAncestors = (collectAncestors' root q []).Value

    lowestCommonAncestor' pAncestors qAncestors System.Int32.MinValue