## Monday, August 8, 2016

### Google – Find Duplicated Subtrees

Related: Check if a Binary Tree contains duplicate subtrees of size 2 or more
Given a binary tree, return all duplicate subtrees.
For example,
``````        1
/ \
2   3
/   / \
4   2   4
/
4
``````
The following are two duplicate subtrees:
``````      2
/
4
``````
and
``````    4
``````
Therefore, return `[ [2,4], [4] ]`.

[Solution]

String curr = dfs(root.left) + root.val + dfs(root.right)

`class` `Solution {`
`  ``int` `cnt = ``0``;`
`  ``public` `int` `duplicatedSubtree(TreeNode root) {`
`    ``if` `(root == ``null``) {`
`      ``return` `0``;`
`    ``}`
`    ``Set<String> trees = ``new` `HashSet<>();`
`    ``dfs(root, trees);`
`    ``return` `cnt;`
`  ``}`
`  ``private` `String dfs(TreeNode root, Set<String> trees) {`
`    ``if` `(root == ``null``) {`
`      ``return` `"#"``;`
`    ``}`
`    ``String left = dfs(root.left, trees);`
`    ``String right = dfs(root.right, trees);`
`    ``String curr = left + root.val + right;`
`    ``if` `(trees.contains(curr)) {`
`      ``cnt++;`
`    ``}`
`    ``else` `{`
`      ``trees.add(curr);`
`    ``}`
`    ``return` `curr;`
`  ``}`
`}`
https://discuss.leetcode.com/topic/19/find-duplicate-subtrees/12