本期的Python學(xué)習(xí)課堂筆記：尋找重復(fù)的子樹

公司主營(yíng)業(yè)務(wù)：成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、移動(dòng)網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競(jìng)爭(zhēng)能力。創(chuàng)新互聯(lián)是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對(duì)我們的高要求，感謝他們從不同領(lǐng)域給我們帶來(lái)的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來(lái)驚喜。創(chuàng)新互聯(lián)推出景洪免費(fèi)做網(wǎng)站回饋大家。

題目:

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

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

示例 1：

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

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

 2
 /
 4

和

 4

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

解題思路：

這就是一道考察二叉樹遍歷的題, 遍歷的時(shí)候序列化作為 String 類型存入 Map, 若其為第二次出現(xiàn)即將該結(jié)點(diǎn)加入數(shù)組.

代碼:

這里以后序遍歷為例, 需要注意葉子結(jié)點(diǎn)應(yīng)當(dāng)規(guī)定一個(gè)特殊字符作為替代 null 結(jié)點(diǎn), 這里用的是 ‘#’

Java:

class Solution {
 public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
 List<TreeNode> list = new ArrayList<>();//待返回?cái)?shù)組
 if (root == null) return list;
 Map<String, Integer> map = new HashMap<>();//哈希映射查找重覆子結(jié)點(diǎn)
 traverse(root, map, list, "");
 return list;
 }
	//后序遍歷
 private String traverse(TreeNode node, Map<String, Integer> map, List<TreeNode> list, String tree) {
 if (node == null) return tree + "#";
 String left = traverse(node.left, map, list, tree);//遞歸左子孩子
 String right = traverse(node.right, map, list, tree);//遞歸右子孩子
 tree = tree + node.val + left + right;//每個(gè)子樹路徑
 map.put(tree, map.getOrDefault(tree, 0) + 1);//存儲(chǔ)每個(gè)子樹路徑
 if (map.get(tree) == 2) list.add(node);//第二次出現(xiàn)相同路徑時(shí)存儲(chǔ)該結(jié)點(diǎn)
 return tree;
 }
}

Python:

class Solution:
 def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
 res = [] # 待返回?cái)?shù)組
 if not root: return res
 hash_map = {} # 哈希映射查找重覆子結(jié)點(diǎn)
 self.traverse(root, hash_map, res, '')
 return res
	# 后序遍歷
 def traverse(self, node: TreeNode, hash_map, res, tree):
 if not node: return tree + '#'
 left = self.traverse(node.left, hash_map, res, tree) # 遞歸左子孩子
 right = self.traverse(node.right, hash_map, res, tree) # 遞歸右子孩子
 tree = tree + str(node.val) + left + right # 每個(gè)子樹路徑
 if tree in hash_map.keys(): # 存儲(chǔ)每個(gè)子樹路徑
 hash_map[tree] += 1
 else:
 hash_map[tree] = 1
 if hash_map[tree] == 2: # 第二次出現(xiàn)相同路徑時(shí)存儲(chǔ)該結(jié)點(diǎn)
 res.append(node)
 return tree

有不清楚的地方可以留言，更多的 Python學(xué)習(xí)課堂筆記也會(huì)繼續(xù)給大家更新！

當(dāng)前題目：Python學(xué)習(xí)課堂筆記：尋找重復(fù)的子樹
標(biāo)題路徑：http://www.chinadenli.net/article42/piseec.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供小程序開發(fā)、靜態(tài)網(wǎng)站、手機(jī)網(wǎng)站建設(shè)、網(wǎng)站收錄、企業(yè)建站、關(guān)鍵詞優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)