652. Find Duplicate Subtrees

Given the root of 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 the same node values.

Example 1:

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

Example 2:

Input: root = [2,1,1]
Output: [[1]]

Example 3:

Input: root = [2,2,2,3,null,3,null]
Output: [[2,3],[3]]

Constraints:

• The number of the nodes in the tree will be in the range [1, 10^4]

• -200 <= Node.val <= 200

Solution

We want to find identical subtrees and add one of them to the return list.

First thought

The first idea is to traverse the nodes and see if any of them are the same. We might use a map which key is node value and value is the list of corresponding nodes.

Whenever we traverse a node, we need to check if they are identical to any of the nodes list.

The time complexity for this is O(N^2) - since in the worst case, the node compared the others N-1 nodes.

Optimal solution

If we organized and classified the sub-tree status and keep them into a data structure. Then next time, we encounter the same structure, we can recognize a duplication here.

So how to organize the tree status? It is a good idea to serialize the tree into a String. by like: L:<L_subTree_serialresult>#<root.val>R:<R_subTree_serialresult> Then we need a property for this serail result in order to keep the corresponding nodes. Therefore, Map<K,V> is adaptable. K(String): serial string, V(List<Nodes>): nodes with the serial result

And we traverse the given tree and keep updating the Map. Once the traversal is over, we can easily find out the cases by checking the map values size.

Map<String, List<TreeNode>> map;
public List<TreeNode> findDuplicated(TreeNode root) {
    map = new HashMap<>();
    serialize(root);
    List<TreeNode> ret = new ArrayList<>();
    for(List<TreeNode> nodes : map.values()) {
        if(nodes.size() >= 2){
            ret.add(nodes.get(0));
        }
    }
    return ret;
}

public String serialize(TreeNode node) {
    if(node == null) return "#";
    String serialResult = "L:" + serialize(node.left) + 
                        "@" + node.val + "R:" + serialize(node.right);
    if(!map.containsKey(serialResult)){
        map.put(serialResult, new LinkedList<TreeNode>());
    }
    map.get(serialResult).add(node);
}