<h2 id="heading-url">URL</h2>
<p><a target="_blank" href="https://leetcode.com/problems/find-duplicate-subtrees/description/">Find Duplicate Subtrees - LeetCode</a></p>
<h2 id="heading-code">Code</h2>
<p><a target="_blank" href="https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/problems/0652/main.fsx">https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/problems/0652/main.fsx</a></p>
<pre><code class="lang-plaintext">type Tree =
    | Leaf
    | Node of int * Tree * Tree

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

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

    findDuplicateSubtrees' root Map.empty [] |&gt; snd
</code></pre>


## URL

[Find Duplicate Subtrees - LeetCode](https://leetcode.com/problems/find-duplicate-subtrees/description/)

## Code

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

```plaintext
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
```

LeetCode 652. Find Duplicate Subtrees in F#

URL

Code