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

My Solutions:

方法1:

traverse树的时候用一个string储存树的结构，用一个map储存string出现的频率。如果频率出现两次，说明发现同样的subtree

class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> res = new LinkedList<>();
        traverse(root, new HashMap<>(), res);
        return res;
    }
    
    public String traverse(TreeNode node, Map<String, Integer> cnt, List<TreeNode> res) {
        if (node == null) return "";
        String rep = "(" + traverse(node.left, cnt, res) + ")" + node.val + "(" + traverse(node.right, cnt, res) + ")";
        cnt.put(rep, cnt.getOrDefault(rep, 0) + 1);
        if (cnt.get(rep) == 2) res.add(node);
        return rep;
    }
}

Complexity Analysis

Let n denote the number of nodes.

Time: O(N * N). The string representation of each subtree can have a length up to O(n). Creating each representation therefore costs up to O(n), and we find string representations for all O(n) subtrees during the traversal.

Space: O(N * N). We store all string representations in the hash map. There are O(n) subtrees, and each subtree representation has the length of O(n).

方法2:

Instead of representing a subtree with a string, we will use non-negative integer IDs: 0, 1, 2, and so on. Two subtrees are equal when they have equal root values, equal left subtrees, and equal right subtrees. Thus one can characterize a tree with the triplet (ID of the left subtree, root value, ID of the right subtree). Equal subtrees have the same triplets.

class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> res = new LinkedList<>();
        traverse(root, new HashMap<>(), new HashMap<>(), res);
        return res;
    }

    public int traverse(TreeNode node, Map<String, Integer> tripletToID,
            Map<Integer, Integer> cnt, List<TreeNode> res) {
        if (node == null return 0;
        String triplet = traverse(node.left, tripletToID, cnt, res) + "," + node.val +
                "," + traverse(node.right, tripletToID, cnt, res);
        if (!tripletToID.containsKey(triplet)) {
            tripletToID.put(triplet, tripletToID.size() + 1);
        }
        int id = tripletToID.get(triplet);
        cnt.put(id, cnt.getOrDefault(id, 0) + 1);
        if (cnt.get(id) == 2) res.add(node);
        return id;
    }
}

因为tripletID的长度是O(1), 所以和方法1相比，方法2的复杂度都是O(N)

Time: O(N)

Space: O(N)