[LeetCode] 652. Find Duplicate Subtrees

轉自LeetCode

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
       /
      4

The following are two duplicate subtrees:

      2
     /
    4

and

    4

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

<Solution>

想法如下

• 因為要重複比較，使用 recursive

• 對於每一個子樹，在 recursive 的過程中，使用一個 unique 的 string 來表達目前的子樹

• 透過這個 unique 的 string 來當作 key，因此，只要這個 key 的值大於一，就是有重複的子樹了

code 如下

Java(參考解法)