package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 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) {
        if (root == null) {
            return new ArrayList<>();
        }
        Map<String, NodeString> left = new HashMap<>();
        build(root.left, left);
        Map<String, NodeString> right = new HashMap<>();
        build(root.right, right);
        List<TreeNode> result = new ArrayList<>();
        for (Map.Entry<String, NodeString> entry : left.entrySet()) {
            if (right.containsKey(entry.getKey())) {
                result.add(entry.getValue().node);
            }
        }
        return result;
    }

    private static class NodeString {
        private final TreeNode node;
        private final String string;

        public NodeString(TreeNode node, String string) {
            this.node = node;
            this.string = string;
        }
    }

    private static NodeString build(TreeNode node, Map<String, NodeString> map) {
        if (node == null) {
            return new NodeString(node, "");
        }
        NodeString left = build(node.left, map);
        NodeString right = build(node.right, map);
        String string = left.string + "," + right.string + "," + node.val;
        NodeString current = new NodeString(node, string);
        map.put(string, current);
        return current;
    }

    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.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(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(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]]
    }
}

@@ -364,101 +364,8 @@
    %7D
-%0A%0A        @Override%0A        public String toString() %7B%0A            return %22%22 + val;%0A        %7D
 %0A   
@@ -521,85 +521,48 @@
     
-Map%3CString, NodeString%3E left = new HashMap%3C%3E();%0A        build(root.left, left
+List%3CTreeNode%3E result = new ArrayList%3C%3E(
 );%0A 
@@ -572,32 +572,37 @@
     Map%3CString, 
+List%3C
 NodeString%3E righ
@@ -596,22 +596,21 @@
 eString%3E
- right
+%3E map
  = new H
@@ -644,271 +644,67 @@
 oot.
-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
+left, map, result);%0A        build(root.right, map, result);
 %0A   
@@ -1045,16 +1045,21 @@
 String, 
+List%3C
 NodeStri
@@ -1061,20 +1061,44 @@
 eString%3E
+%3E
  map
+, List%3CTreeNode%3E result
 ) %7B%0A    
@@ -1218,24 +1218,32 @@
 de.left, map
+, result
 );%0A        N
@@ -1281,16 +1281,24 @@
 ght, map
+, result
 );%0A     
@@ -1438,653 +1438,201 @@
     
-map.put(string, current);%0A        return current;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem652 prob = new Problem652();%0A%0A        TreeNode root = new TreeNode(1);%0A        root.left = new TreeNode(2);%0A        root.left.left = new TreeNode(4);%0A        root.left.right = new TreeNode(5);%0A        root.right = new TreeNode(3);%0A        root.right.left = new TreeNode(2);%0A        root.right.left.left = new TreeNode(4);%0A        root.right.left.right = new TreeNode(5);%0A        root.right.right = new TreeNode(4);%0A        System.out.println(prob.findDuplicateSubtrees(root)); // %5B%5B2,4,5%5D,%5B4%5D,%5B5%5D%5D%0A%0A        root = new TreeN
+if (map.containsKey(string)) %7B%0A            List%3CNodeString%3E nodes = map.get(string);%0A            nodes.add(current);%0A            if (nodes.size() == 2) %7B%0A                result.add(current.n
 ode
-(1
 );%0A 
@@ -1642,519 +1642,152 @@
     
-root.left = new TreeNode(2);%0A        root.left.left = new TreeNode(4);%0A        root.right = new TreeNode(3);%0A        root.right.left = new TreeNode(2);%0A        root.right.left.left = new TreeNode(4);%0A        root.right.right = new TreeNode(4);%0A        System.out.println(prob.findDuplicateSubtrees(root)); // %5B%5B2,4%5D,%5B4%5D%5D%0A%0A        root = new TreeNode(1);%0A        root.left = new TreeNode(2);%0A        root.left.left = new TreeNode(2);%0A        root.right = new TreeNode(3);%0A        root.right.left = new TreeNode(2
+    %7D%0A        %7D else %7B%0A            List%3CNodeString%3E nodes = new ArrayList%3C%3E();%0A            nodes.add(current);%0A            map.put(string, nodes
 );%0A 
@@ -1797,168 +1797,33 @@
     
-root.right.left.left = new TreeNode(2);%0A        root.right.right = new TreeNode(4);%0A        System.out.println(prob.findDuplicateSubtrees(root)); // %5B%5B2,2%5D,%5B2%5D%5D
+%7D%0A        return current;
 %0A   

Solve problem 652