# 652. Find Duplicate Subtrees

## how to serialization

序列化: root + "," + s(root.left) + "," + s(root.right)

xx

xxx

因為對子樹做操作, so use postorder

## postorder dfs, serialization with String

Can anyone explain how the first solution is O(n^2)? My understanding is that it pretty much does the same thing as second solution. Arent both O(n) - n being number of nodes in the tree?

Edit:

I understand now. Since strings are bring used, the concatenation takes O(n) time in each recursive call taking overall complexity to O(n2).\
<https://stackoverflow.com/questions/15400508/string-concatenation-complexity-in-c-and-java>

雖然 DFS  是 O(n), 但字串串接時用 String, 所以串接會是 O(n), 所以是 O(n^2)

use StringBuilder 應該就沒字串串接 O(n) 這問題, 但問題還是在於 hash , 如果字太長了 , hash 也會變成 從 O(1) -> O(n),  (這題數量可以到&#x20;

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

), 所以是 dfs \* String hash =  O(n^2)

[@shiyuluu](https://leetcode.com/shiyuluu) is right. Concatenating in string isn't a main problem here. The problem is building hash from all seeing nodes fast.&#x20;

If you want to build a hash from a string, you have to go through all the letters of that string. Each letter of this string is one node. Therefore, the first solution has a complexity of n ^ 2.

T: O(n^2)

S: O(n..larger)

```java
class Solution {
    
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        Map<String, Integer> map = new HashMap<>();
        List<TreeNode> res = new ArrayList<>();
        serialization(root, map, res);
        return res;
    }
    private String serialization(TreeNode root, Map<String, Integer> map, List<TreeNode> res) {
        if (root == null) {
            return "#";
        }
        String key = root.val + "," + serialization(root.left, map, res) + "," + serialization(root.right, map, res);
        map.put(key, map.getOrDefault(key,0)+1);
        if (map.get(key) == 2) {
            res.add(root);
        }
        return key;
    }
}
```

## postorder dfs + serialization + int id (識別符

![](/files/iw3DZSDp0iB0BkKdqFW7)

Map\<String key, global number> , when add new key, global number++

Map\<global number, count

T: O(n)

Ｓ: O(n..larger)

We can improve this to O(n) by replacing full serializations with serial ids instead.

關鍵是 private int serialization, serialization 回來的是 int, 這樣就可以避免用 string 來做&#x20;

serialization

所以雖然這也還是用 String, Integer , Map\<String, Integer>

但因為 String key 會很短了, root.val + "int id" + "int id"

所以整個 serialization 過程就不會很久

```java
class Solution {
    
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        Map<String, Integer> countMap = new HashMap<>();
        Map<String, Integer> idMap = new HashMap<>();

        List<TreeNode> res = new ArrayList<>();
        serialization(root, idMap, countMap, res);
        return res;
    }
    // the num of nodes can be 10^4, so serialization string may be too long, it casues hashmap confliction
    // the goal is reduce serialization string to a "short id"
    private int serialization(TreeNode root, Map<String, Integer> idMap, Map<String, Integer> countMap, List<TreeNode> res) {
        if (root == null) {
            return -1;
        }
        String key = root.val + "," + 
            serialization(root.left, idMap, countMap, res) + "," + 
            serialization(root.right, idMap, countMap, res);
        
        if (!idMap.containsKey(key)) {
            // when there is new key to add, idMap.size() will increase, so it's a unique number
            // idMap.size() be the short id, or use a global variable is also ok
            idMap.put(key, idMap.size()); 
            
            countMap.put(key, 1); // countMap part is just like solution1's map
        } else {
            countMap.put(key, countMap.get(key)+1);
            if (countMap.get(key) == 2) {
                res.add(root);
            }
        }
        return idMap.get(key); // return uid
    }

}
```

#### these 3 line can to one line

```
//int uid = uidMap.computeIfAbsent(serial, x-> t++); // 如果是有這個 key, 用原本的值, 沒有才回傳 t++加玩的結果
        
int uid = serialToUidMap.getOrDefault(serial, t);
if (uid == t) t++;
serialToUidMap.put(serial, uid);

for 不同的 key(很短的 serial), 給一個新的 uid, 最後回傳的也是 uid, 這樣序列化整個的結果會很短

一樣的 key 還是用原本的 value(uid)

不過要注意 uidMap.computeIfAbsent(serial, x-> t++)
這個 t 要全域變數
```

```java
class Solution {
    int t;
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        t = 1;
        Map<String, Integer> serializeToUidMap = new HashMap<>(); // <string key, uid>
        Map<Integer, Integer> uidToCountMap = new HashMap<>(); // <uid, count>
        List<TreeNode> res = new ArrayList<>();
        
        serialize(root, serializeToUidMap, uidToCountMap, res);
        return res;
    }
    
    private int serialize(TreeNode node, Map<String, Integer> serializeToUidMap,
                         Map<Integer, Integer> uidToCountMap, List<TreeNode> res) {
        if (node == null) {
            return 0;
        }
        String serializedStr = node.val + "," +
            serialize(node.left, serializeToUidMap, uidToCountMap, res) + "," +
            serialize(node.right, serializeToUidMap, uidToCountMap, res);
        
        int uid = serializeToUidMap.computeIfAbsent(serializedStr, k -> t++);
        
        uidToCountMap.put(uid, uidToCountMap.getOrDefault(uid, 0) + 1);
        if (uidToCountMap.get(uid) == 2) {
            res.add(node);
        }
        return uid;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/tree/652.-find-duplicate-subtrees.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.