1.題目描述
給定一棵二叉樹 root阻逮，返回所有重復(fù)的子樹。
對于同一類的重復(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]]
2.解題思路與代碼
2.1 解題思路
這道題需要找到重復(fù)的子樹界酒， 我們使用 DFS 進(jìn)行二叉樹遍歷纠屋，并且在遍歷的同時對遍歷的路徑進(jìn)行序列化成字符串，節(jié)點(diǎn)間用符號 “-” 進(jìn)行分割盾计。同時售担，我們使用一個 HashMap 來存放路徑及該路徑出現(xiàn)的次數(shù)赁遗。在對每個節(jié)點(diǎn)進(jìn)行左右子節(jié)點(diǎn)遍歷完成后，表示當(dāng)前節(jié)點(diǎn)的子樹路徑已經(jīng)序列化成了字符串族铆，這個時候?qū)⒙窂椒湃?HashMap 中岩四，并且路徑計(jì)數(shù)加 1 。放入 HashMap 之后哥攘，這個時候需要判斷 HashMap 中對應(yīng)路徑的數(shù)量是否為 2 剖煌，如果為 2 則將當(dāng)前節(jié)點(diǎn)放入結(jié)果列表中，由于子樹存在重復(fù)的情況逝淹，如果僅僅判斷路徑是否存在則會導(dǎo)致重復(fù)統(tǒng)計(jì)耕姊，因此這里只判斷是否為 2。從根節(jié)點(diǎn)開始 DFS 完成上面操作栅葡，最后返回結(jié)果列表即可茉兰。
2.2 代碼
class Solution {
List<TreeNode> ans = new ArrayList<>();
Map<String, Integer> map = new HashMap<>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
process(root);
return ans;
}
public String process(TreeNode node) {
if (node == null) {
return "-";
}
StringBuilder builder = new StringBuilder(String.valueOf(node.val));
builder.append("-");
String left = process(node.left);
String right = process(node.right);
builder.append(left).append(right);
map.put(builder.toString(), map.getOrDefault(builder.toString(), 0) + 1);
if (map.get(builder.toString()) == 2) {
ans.add(node);
}
return builder.toString();
}
}
2.3 測試結(jié)果
通過測試
測試結(jié)果
3.總結(jié)
- 使用深度優(yōu)先對二叉樹進(jìn)行遍歷，并且在遍歷時對節(jié)點(diǎn)路徑進(jìn)行序列化
- 使用哈希表來存放節(jié)點(diǎn)的路徑及改路徑出現(xiàn)的次數(shù)
