This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any **one** of them.

Two trees are duplicate if they have the same structure with same node values.

**Example 1: **

1 / \ 2 3 / / \ 4 2 4 / 4The following are two duplicate subtrees:

2 / 4and

4Therefore, you need to return above trees' root in the form of a list.

b'

\n\n

\n#### Approach #1: Depth-First Search [Accepted]

\n\n

\n#### Approach #2: Unique Identifier [Accepted]

\n

\n

'
\n

**Intuition**

We can serialize each subtree. For example, the tree

\n1\n / \\\n 2 3\n / \\\n 4 5\n

can be represented as the serialization `1,2,#,#,3,4,#,#,5,#,#`

, which is a unique representation of the tree.

**Algorithm**

Perform a depth-first search, where the recursive function returns the serialization of the tree. At each node, record the result in a map, and analyze the map after to determine duplicate subtrees.

\n\n**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the number of nodes in the tree. We visit each node once, but each creation of

\n`serial`

may take work. \n - \n
Space Complexity: , the size of

\n`count`

. \n

\n

**Intuition**

Suppose we have a unique identifier for subtrees: two subtrees are the same if and only if they have the same id.

\nThen, for a node with left child id of `x`

and right child id of `y`

, `(node.val, x, y)`

uniquely determines the tree.

**Algorithm**

If we have seen the triple `(node.val, x, y)`

before, we can use the identifier we\'ve remembered. Otherwise, we\'ll create a new one.

**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the number of nodes in the tree. We visit each node once.

\n \n - \n
Space Complexity: . Every structure we use is using storage per node.

\n \n

\n

Analysis written by: @awice. Approach #2 inspired by @StefanPochmann.

\n