LeetCode : 652. Find Duplicate Subtrees

[congr]

https://leetcode.com/problems/find-duplicate-subtrees/

[congr]

O(N^2)

[congr]

/**
 * 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) {
        Map<String, Integer> map = new HashMap();
        List<TreeNode> list = new ArrayList();

        buildString(root, map, list);

        return list;
    }

    String buildString(TreeNode root, Map<String, Integer> map, List<TreeNode> list) {
        if (root == null) return "$";

        String s = root.val + " " + 
            buildString(root.left, map, list) + " " + 
            buildString(root.right, map, list) + " ";

        if (map.merge(s, +1, Integer::sum) == 2) list.add(root);

        return s;
    }
}

[congr]

Similar questions

Serialize and Deserialize Binary Tree Serialize and Deserialize BST Construct String from Binary Tree