> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/binary_tree_and_divide_conquer/order-traversal/find-duplicate-subtrees.md).

# Find Duplicate Subtrees

<https://leetcode.com/problems/find-duplicate-subtrees/description/>

> 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.

## Thoughts

先尝试分治，并不行，因为左右子树重复的树可能并不在它们各自返回的结果里，还是需要重新访问左右子树查抄有没有相同的。后来看到别人的解法，和Serialize思路类似，把每个子树转成string, 只是这里要把每个substring都记录下来。看到有些人在争论是先序还是后序。虽然写法看上去是先序，但由于是左右子树先返回然后再加的当前结点，所以实际上是后序。

## Code

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private String postOrder(TreeNode node, Map<String, Integer> strings, List<TreeNode> res) {
        if (node == null) {
            return "#";
        }
        String str = node.val + "," + postOrder(node.left, strings, res) + "," + postOrder(node.right, strings, res);
        if (strings.getOrDefault(str, 0) == 1) {
            res.add(node);
        }
        strings.put(str, strings.getOrDefault(str, 0) + 1);;
        return str;
    }

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> res = new ArrayList<>();
        postOrder(root, new HashMap<>(), res);
        return res;
    }
}
```

## Analysis

时间复杂度为一次后续遍历，O(n)。

## Ver.2

同样原理iterative实现. 需要把每个节点对应的string存下来, 因此需要额外的map.

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private final String NULL = "#";
    private final String SPLITER = "/";

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        Map<String, Integer> freqs = new HashMap<>();
        Map<TreeNode, String> map = new HashMap<>();
        map.put(null, NULL + SPLITER);
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root, pre = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            TreeNode node = stack.peek();
            if (!map.containsKey(node)) {
                map.put(node, node.val + SPLITER);
            }
            map.put(node, map.get(node) + map.get(pre));

            if (node.right != null && node.right != pre) {
                pre = null;
                cur = node.right;
                continue;
            }
            String sub = map.get(node);
            if (node.right == null) {
                map.put(node, sub + NULL + SPLITER);
            }
            //System.out.println(map.get(node));
            pre = stack.pop();
            freqs.put(map.get(node), freqs.getOrDefault(map.get(node), 0) + 1);
            if (freqs.get(map.get(node)) == 2) {
                res.add(node);
            }
        }

        return res;
    }
}
```