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

Two trees are duplicate if they have the same structure with same node values.

**Example 1: **

tree

The following are two duplicate subtrees:

subtree

and

subtree

Therefore, you need to return above trees' root in the form of a list.

Solution

Serialize tree, time O(nlogn)? space O(nlogn)?

题目并不难，把每个subtree的根节点存入一个HashMap中，然后递归判断root是否跟HashMap中的节点为duplicate。但这样计算会TLE，因为判断两个TreeNode是否为duplicate的代价比较大。比较方便的做法是将tree序列化成String，然后判断String是否相同即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> duplicates = new LinkedList<>();
        Map<String, Integer> map = new HashMap<>();
        findDuplicateSubtreesRecur(root, map, duplicates);
        return duplicates;
    }
    
    public void findDuplicateSubtreesRecur(TreeNode root, Map<String, Integer> map, List<TreeNode> duplicates) {
        if (root == null) {
            return;
        }
        
        String s = serialize(root);
        if (map.getOrDefault(s, 0) == 1) {
            duplicates.add(root);
        }
        map.put(s, map.getOrDefault(s, 0) + 1);
        
        findDuplicateSubtreesRecur(root.left, map, duplicates);
        findDuplicateSubtreesRecur(root.right, map, duplicates);
    }
    
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }
    
    public void serialize(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append("#");
            return;
        }
        
        sb.append(root.val);
        serialize(root.left, sb);
        serialize(root.right, sb);
    }
}