URL

Find Duplicate Subtrees - LeetCode

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/problems/0652/main.fsx

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

let findDuplicateSubtrees (root: Tree) : Tree list =
    let rec findDuplicateSubtrees' node acc ret =
        match node with
        | Leaf -> acc, ret
        | Node(_, left, right) ->
            let acc', ret' = findDuplicateSubtrees' left acc ret
            let acc'', ret'' = findDuplicateSubtrees' right acc' ret'

            match Map.tryFind node acc'' with
            | Some(v) ->
                if v = 1 then
                    Map.add node (v + 1) acc'', node :: ret''
                else
                    acc'', ret''
            | None -> Map.add node 1 acc'', ret''

    findDuplicateSubtrees' root Map.empty [] |> snd