package leetcode;

import java.util.List;

/**
 * https://leetcode.com/problems/find-duplicate-subtrees/
 */
public class Problem652 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return "" + val;
        }
    }

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        // TODO
        return null;
    }

    public static void main(String[] args) {
        Problem652 prob = new Problem652();

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(2);
        root.right.left.left = new TreeNode(4);
        root.right.right = new TreeNode(4);
        System.out.println(prob.findDuplicateSubtrees(root)); // [[2,4],[4]]

        root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(2);
        root.right.left.left = new TreeNode(4);
        root.right.left.right = new TreeNode(5);
        root.right.right = new TreeNode(4);
        System.out.println(prob.findDuplicateSubtrees(root)); // [[2,4,5],[4],[5]]

        root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(2);
        root.right.left.left = new TreeNode(2);
        root.right.right = new TreeNode(4);
        System.out.println(prob.findDuplicateSubtrees(root)); // [[2,2],[2]]
    }
}

@@ -29,20 +29,96 @@
 va.util.
-List
+ArrayList;%0Aimport java.util.HashMap;%0Aimport java.util.List;%0Aimport java.util.Map
 ;%0A%0A/**%0A 
@@ -538,35 +538,1241 @@
     
-// TODO%0A        return null
+if (root == null) %7B%0A            return new ArrayList%3C%3E();%0A        %7D%0A        Map%3CString, NodeString%3E left = new HashMap%3C%3E();%0A        build(root.left, left);%0A        Map%3CString, NodeString%3E right = new HashMap%3C%3E();%0A        build(root.right, right);%0A        List%3CTreeNode%3E result = new ArrayList%3C%3E();%0A        for (Map.Entry%3CString, NodeString%3E entry : left.entrySet()) %7B%0A            if (right.containsKey(entry.getKey())) %7B%0A                result.add(entry.getValue().node);%0A            %7D%0A        %7D%0A        return result;%0A    %7D%0A%0A    private static class NodeString %7B%0A        private final TreeNode node;%0A        private final String string;%0A%0A        public NodeString(TreeNode node, String string) %7B%0A            this.node = node;%0A            this.string = string;%0A        %7D%0A    %7D%0A%0A    private static NodeString build(TreeNode node, Map%3CString, NodeString%3E map) %7B%0A        if (node == null) %7B%0A            return new NodeString(node, %22%22);%0A        %7D%0A        NodeString left = build(node.left, map);%0A        NodeString right = build(node.right, map);%0A        String string = left.string + %22,%22 + right.string + %22,%22 + node.val;%0A        NodeString current = new NodeString(node, string);%0A        map.put(string, current);%0A        return current
 ;%0A  
@@ -1978,32 +1978,75 @@
 ew TreeNode(4);%0A
+        root.left.right = new TreeNode(5);%0A
         root.rig
@@ -2150,32 +2150,81 @@
 ew TreeNode(4);%0A
+        root.right.left.right = new TreeNode(5);%0A
         root.rig
@@ -2321,21 +2321,27 @@
 // %5B%5B2,4
+,5
 %5D,%5B4%5D
+,%5B5%5D
 %5D%0A%0A     
@@ -2450,51 +2450,8 @@
 4);%0A
-        root.left.right = new TreeNode(5);%0A
     
@@ -2579,57 +2579,8 @@
 4);%0A
-        root.right.left.right = new TreeNode(5);%0A
     
@@ -2685,35 +2685,29 @@
 )); // %5B%5B2,4
-,5
 %5D,%5B4%5D
-,%5B5%5D
 %5D%0A%0A        r

Update problem 652