力扣(LeetCode)652

Noodles 發(fā)布于2019-08-16 14:27 / 1834人閱讀

摘要：對于同一類的重復(fù)子樹，你只需要返回其中任意一棵的根結(jié)點(diǎn)即可。兩棵樹重復(fù)是指它們具有相同的結(jié)構(gòu)以及相同的結(jié)點(diǎn)值。這里再用存儲(chǔ)，鍵序列化結(jié)果，值樹節(jié)點(diǎn)組成的鏈表。

題目地址：
https://leetcode-cn.com/probl...
題目描述：
給定一棵二叉樹，返回所有重復(fù)的子樹。對于同一類的重復(fù)子樹，你只需要返回其中任意一棵的根結(jié)點(diǎn)即可。

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

示例 1：

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

  2
 /
4

和

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

解答：
如何判斷兩棵樹是重復(fù)的？只要兩棵樹的先序(各種序都可以)遍歷結(jié)果是一樣的，那么這兩棵樹就是重復(fù)的？
不一定！！！

  2
 /
4

和
2

4
它們的先序遍歷結(jié)果就是相同的，但是并不重復(fù)。為什么？因?yàn)楸闅v的時(shí)候忽略掉了空樹的位置。
但是如果先序訪問這個(gè)樹的時(shí)候保留空樹(也就是訪問空樹)，那么此時(shí)就成立了！先序遍歷樹并
且對它進(jìn)行序列化，空樹的序列化結(jié)果為" "，而對于任意節(jié)點(diǎn)root它的序列化結(jié)果為"root.val 左子樹序列化右子樹序列化"。這里再用hashmap存儲(chǔ)，鍵：序列化結(jié)果，值：樹節(jié)點(diǎn)組成的鏈表。最后序列化完，遍歷這個(gè)hashmap，找到hashmap中，值(鏈表)長度大于1的位置，把這個(gè)位置鏈表的第一個(gè)節(jié)點(diǎn)放入答案集，按照這個(gè)思路就能理解下面的代碼：
java ac代碼：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    HashMap> map = new HashMap(1000);

    public List findDuplicateSubtrees(TreeNode root) {
        serialize(root);
        List ans = new ArrayList(1000);
        for(Map.Entry> entry:map.entrySet())
            if(entry.getValue().size()>1)
            ans.add(entry.getValue().get(0) );
        return ans;
    }
    
    public String serialize(TreeNode root)
    {
        if(root == null)return " ";
        String temp = root.val+" "+serialize(root.left)+" "+serialize(root.right);
        if(map.get(temp) == null){
            List list = new LinkedList();
            list.add(root);
            map.put(temp,list);
        }
        else map.get(temp).add(root);
        return temp;
    }
    
}