LeetCode #652 Find Duplicate Subtrees

Medium

Problem

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

Postorder traverse this tree and save results of each subtree as hash key. Once it found there is a repeated key, dump the node into result list.

Complexity

Because of postorder traversal, it takes O(n) time to run entire tree, where n denotes to counts of nodes in this tree. At each iteration, it takes O(1)/O(logn) time for search for and insert into a hash map in average/worst cases. Therefore, its time complexity will be O(n)/O(nlogn) in average/worst cases.

For space complexity, the hash map needs O(n) extra space for saving key of each node in this tree.