題目鏈接

給定一棵二叉樹(shù)剪菱，返回所有重復(fù)的子樹(shù)。對(duì)于同一類(lèi)的重復(fù)子樹(shù)篮绿，你只需要返回其中任意一棵的根結(jié)點(diǎn)即可。

兩棵樹(shù)重復(fù)是指它們具有相同的結(jié)構(gòu)以及相同的結(jié)點(diǎn)值吕漂。

示例 1：

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4

下面是兩個(gè)重復(fù)的子樹(shù)：

      2
     /
    4

和

    4

因此搔耕，你需要以列表的形式返回上述重復(fù)子樹(shù)的根結(jié)點(diǎn)。

解答

超時(shí)版本

`public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> res = new ArrayList<>();
        getAllTrees(root);
        boolean[] isAdded = new boolean[allTrees.size()];   // 用于標(biāo)識(shí)當(dāng)前子樹(shù)是否已是相同的子樹(shù)
        for (int i = 0; i < allTrees.size(); i++) {
            TreeNode node1 = allTrees.get(i);
            for (int j = i+1; j < allTrees.size(); j++) {
                TreeNode node2 = allTrees.get(j);
                if (isSameTree(node1, node2)) {
                    if (!isAdded[i] && !isAdded[j]) res.add(node1);
                    isAdded[i] = true;
                    isAdded[j] = true;
                }
            }
        }
        return res;
    }

    // 獲取樹(shù)中所有子樹(shù)
    List<TreeNode> allTrees = new ArrayList<>();
    public void getAllTrees(TreeNode root) {
        if (root != null) {
            allTrees.add(root);
            getAllTrees(root.left);
            getAllTrees(root.right);
        }
    }

    public boolean isSameTree(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) return true;
        if (node1 == null && node2 != null || node1 != null && node2 == null) return false;
        return node1.val == node2.val && isSameTree(node1.left, node2.left) && isSameTree(node1.right, node2.right);
    }

優(yōu)化后的序列化版本

Map<String, Integer> treeMap = new HashMap<>(); // 用于統(tǒng)計(jì)不同樹(shù)結(jié)構(gòu)與其出現(xiàn)的次數(shù)
    List<TreeNode> trees = new ArrayList<>();       // 結(jié)果
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        findSameTreesInTraversal(root);
        return trees;
    }

    public String findSameTreesInTraversal(TreeNode node) {
        // 序列化當(dāng)前節(jié)點(diǎn)的樹(shù)痰娱，將其加入到treeMap中
        StringBuilder sb = new StringBuilder();
        if (node == null) return "";
        sb.append(',').append(node.val).append(',').append(findSameTreesInTraversal(node.left))
                .append(',').append(findSameTreesInTraversal(node.right));
        treeMap.put(sb.toString(), treeMap.getOrDefault(sb.toString(), 0)+1);
        if (treeMap.get(sb.toString()) == 2) trees.add(node);
        return sb.toString();
    }