給定一棵二叉樹 root锥涕，返回所有重復(fù)的子樹扶认。
對(duì)于同一類的重復(fù)子樹请琳，你只需要返回其中任意一棵的根結(jié)點(diǎn)即可粱挡。
如果兩棵樹具有相同的結(jié)構(gòu)和相同的結(jié)點(diǎn)值，則它們是重復(fù)的俄精。
示例 1：
輸入：root = [1,2,3,4,null,2,4,null,null,4]
輸出：[[2,4],[4]]
示例 2：
輸入：root = [2,1,1]
輸出：[[1]]
示例 3：
輸入：root = [2,2,2,3,null,3,null]
輸出：[[2,3],[3]]
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/find-duplicate-subtrees
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有询筏。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處竖慧。
方法一：暴力
遍歷整個(gè)樹嫌套，每個(gè)結(jié)點(diǎn)都添加到list集合中，最后再來(lái)比較每個(gè)是否有重復(fù)的
方法二：三元組優(yōu)化
三元組優(yōu)化了空間時(shí)間圾旨，利用編號(hào)代替了每個(gè)結(jié)點(diǎn)的子節(jié)點(diǎn)踱讨，節(jié)省了大量的時(shí)間和空間，相等的結(jié)點(diǎn)編號(hào)相同碳胳。
- 思路：
- 深搜搜到葉子結(jié)點(diǎn)勇蝙，然后從葉子節(jié)點(diǎn)網(wǎng)上回溯，就能知道每個(gè)結(jié)點(diǎn)的子節(jié)點(diǎn)情況（就能判斷該結(jié)點(diǎn)是否重復(fù)）挨约，空結(jié)點(diǎn)編號(hào)為0
- 用一個(gè)三元數(shù)組唯一標(biāo)識(shí)一個(gè)結(jié)點(diǎn)味混，[當(dāng)前結(jié)點(diǎn)value,左結(jié)點(diǎn)編號(hào)，右結(jié)點(diǎn)編號(hào)]
- 利用map判斷當(dāng)前三元組是否出現(xiàn)過(guò)诫惭，
- 通過(guò)結(jié)構(gòu)體將樹和當(dāng)前樹根節(jié)點(diǎn)的編號(hào)值存儲(chǔ)起來(lái)
- map<三元組翁锡，結(jié)構(gòu)體>
java代碼實(shí)現(xiàn)（詳細(xì)注釋）
class Solution {
Map<String, Pair<TreeNode,Integer>> map = new HashMap<>();
Set<TreeNode> set = new HashSet<>(); //用來(lái)存儲(chǔ)重復(fù)的子樹
int index = 0; //記錄每個(gè)樹的編號(hào)
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
DFS(root);
List<TreeNode> list = new ArrayList<>(set);
return list;
}
private int DFS(TreeNode root) {
//0.遞歸先寫出口
if (root == null) {
return 0;
}
//1.得到遞歸遍歷得到三元組，并轉(zhuǎn)化為字符串
int[] Three = {root.val, DFS(root.left), DFS(root.right)};
String Key = Arrays.toString(Three); //
//2.先判斷當(dāng)前結(jié)點(diǎn)是否存在
if (map.containsKey(Key)) {//存在
//3.說(shuō)明當(dāng)前結(jié)點(diǎn)重復(fù)了,將當(dāng)前結(jié)點(diǎn)添加到set集合中夕土，并且當(dāng)前結(jié)點(diǎn)已經(jīng)存在馆衔，那么就不需要再創(chuàng)建新的編號(hào)
Pair<TreeNode, Integer> pair = map.get(Key);
set.add(pair.getKey());
return pair.getValue();
} else {//不在哈希表中
//4.將當(dāng)前結(jié)點(diǎn)添加到哈希表中瘟判，并且創(chuàng)建新的編號(hào)
map.put(Key,new Pair<>(root,++index));
return index;
}
}
}
