652. Find Duplicate Subtrees - Medium

前往題目

想法

• 每個可能都比較，不過至少會需要$O(N^2)$

思路

以空間換取時間，把走過的每個路徑都記錄下來，相同路徑就是duplicate

1. preorder，其餘迭代順序也可以
2. 遇到null就回傳null，路徑用字串紀錄
3. 遇到相同路徑（字串）就加入根節點到結果

Code

class Solution {
    Map<String, Integer> map;
    List<TreeNode> res;
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        map = new HashMap();
        res = new ArrayList();
        preorder(root);
        return res;
    }

    private String preorder(TreeNode node) {
        if (node == null) return "null";

        // Assemble current tree
        String s = String.join(",", String.valueOf(node.val), preorder(node.left), preorder(node.right));

        // Found duplicate
        if (map.get(s) != null && map.get(s) == 1) {
            res.add(node);
        }

        // Add to the map
        map.put(s, map.getOrDefault(s, 0) + 1);

        return s;
    }
}