資訊專(zhuān)欄INFORMATION COLUMN
摘要：對(duì)于同一類(lèi)的重復(fù)子樹(shù)，你只需要返回其中任意一棵的根結(jié)點(diǎn)即可。兩棵樹(shù)重復(fù)是指它們具有相同的結(jié)構(gòu)以及相同的結(jié)點(diǎn)值。這里再用存儲(chǔ)，鍵序列化結(jié)果，值樹(shù)節(jié)點(diǎn)組成的鏈表。
題目地址：
https://leetcode-cn.com/probl...
題目描述：
給定一棵二叉樹(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ù)是重復(fù)的？只要兩棵樹(shù)的先序(各種序都可以)遍歷結(jié)果是一樣的，那么這兩棵樹(shù)就是重復(fù)的？
不一定?。。?/p>
2 / 4
和
2
4
它們的先序遍歷結(jié)果就是相同的，但是并不重復(fù)。為什么？因?yàn)楸闅v的時(shí)候忽略掉了空樹(shù)的位置。
但是如果先序訪(fǎng)問(wèn)這個(gè)樹(shù)的時(shí)候保留空樹(shù)(也就是訪(fǎng)問(wèn)空樹(shù))，那么此時(shí)就成立了！先序遍歷樹(shù)并
且對(duì)它進(jìn)行序列化，空樹(shù)的序列化結(jié)果為" "，而對(duì)于任意節(jié)點(diǎn)root它的序列化結(jié)果為"root.val 左子樹(shù)序列化 右子樹(shù)序列化"。這里再用hashmap存儲(chǔ)，鍵：序列化結(jié)果，值：樹(shù)節(jié)點(diǎn)組成的鏈表。最后序列化完，遍歷這個(gè)hashmap，找到hashmap中，值(鏈表)長(zhǎng)度大于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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/73010.html
摘要：文章目錄題目示例說(shuō)明限制解法一分析實(shí)現(xiàn)復(fù)雜度題目給定一棵二叉樹(shù)的根節(jié)點(diǎn)，請(qǐng)返回所有的重復(fù)子樹(shù)。示例示例輸入輸出示例輸入輸出示例輸入輸出說(shuō)明來(lái)源力扣鏈接限制二叉樹(shù)中的節(jié)點(diǎn)數(shù)量在之間。 ...
摘要：圖因此可以成為樹(shù)，在所有可能的樹(shù)中，具有最小高度的樹(shù)被稱(chēng)為最小高度樹(shù)。給出這樣的一個(gè)圖，寫(xiě)出一個(gè)函數(shù)找到所有的最小高度樹(shù)并返回他們的根節(jié)點(diǎn)。因此使用一個(gè)數(shù)組代表每個(gè)節(jié)點(diǎn)的入度，若入度為就是葉子節(jié)點(diǎn)。 題目地址：https://leetcode-cn.com/probl...題目描述： 對(duì)于一個(gè)具有樹(shù)特征的無(wú)向圖，我們可選擇任何一個(gè)節(jié)點(diǎn)作為根。圖因此可以成為樹(shù)，在所有可能的樹(shù)中，具有最小...
摘要：關(guān)于遞歸這里提一兩點(diǎn)遞歸基本有這幾步遞歸的模板，終止條件，遞歸調(diào)用，邏輯處理。 ?作者簡(jiǎn)介：大家好，我是車(chē)神哥，府學(xué)路18號(hào)的車(chē)神? ?個(gè)人主頁(yè)：應(yīng)無(wú)所住而生...
摘要：對(duì)于每個(gè)氣球，提供的輸入是水平方向上，氣球直徑的開(kāi)始和結(jié)束坐標(biāo)?？梢陨涑龅墓臄?shù)量沒(méi)有限制。弓箭一旦被射出之后，可以無(wú)限地前進(jìn)。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數(shù)量。解答這是一道區(qū)間覆蓋問(wèn)題，不太好說(shuō)清楚，利用模板即可。 題目地址：https://leetcode-cn.com/probl...題目描述：在二維空間中有許多球形的氣球。對(duì)于每個(gè)氣球，提供的輸入是水平方...
閱讀 1127·2021-11-22 15:35
閱讀 1759·2021-10-26 09:49
閱讀 3303·2021-09-02 15:11
閱讀 2142·2019-08-30 15:53
閱讀 2698·2019-08-30 15:53
閱讀 2991·2019-08-30 14:11
閱讀 3584·2019-08-30 12:59
閱讀 3303·2019-08-30 12:53
