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 target acc =
        match node with
        | Leaf -> [], false
        | Node (v, left, right) ->
            let acc' = v :: acc

            if v = target then
                acc' |> List.rev, true
            else
                match collectAncestors left target acc' with
                | acc'', true -> acc'', true
                | _, _ -> collectAncestors right target acc'

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

    let pAncestors, _ = collectAncestors root p []
    let qAncestors, _ = collectAncestors root q []

    lowestCommonAncestor' pAncestors qAncestors -1