URL

leetcode.com/problems/two-sum-iv-input-is-a..

Code

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

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

let findTarget (root: Tree) (k: int) : bool =
    let rec collectValues node vals =
        match node with
        | Leaf -> vals
        | Node (v, left, right) ->
            let vals' =
                match Map.tryFind v vals with
                | Some (w) -> Map.add v (w + 1) vals
                | None -> Map.add v 1 vals

            let vals'' = collectValues left vals'
            collectValues right vals''

    let vals = collectValues root Map.empty

    vals
    |> Map.fold
        (fun acc key _ ->
            if acc then
                acc
            else
                let diff = k - key

                match Map.tryFind diff vals with
                | None -> false
                | Some (w) -> if key = diff then w >= 2 else true)
        false