本期的Python學習課堂筆記:尋找重復的子樹
公司主營業(yè)務:成都網站設計、成都網站制作、移動網站開發(fā)等業(yè)務。幫助企業(yè)客戶真正實現互聯網宣傳,提高企業(yè)的競爭能力。創(chuàng)新互聯是一支青春激揚、勤奮敬業(yè)、活力青春激揚、勤奮敬業(yè)、活力澎湃、和諧高效的團隊。公司秉承以“開放、自由、嚴謹、自律”為核心的企業(yè)文化,感謝他們對我們的高要求,感謝他們從不同領域給我們帶來的挑戰(zhàn),讓我們激情的團隊有機會用頭腦與智慧不斷的給客戶帶來驚喜。創(chuàng)新互聯推出景洪免費做網站回饋大家。
題目:
給定一棵二叉樹,返回所有重復的子樹。對于同一類的重復子樹,你只需要返回其中任意 一棵的根結點即可。
兩棵樹重復是指它們具有相同的結構以及相同的結點值。
示例 1:
1 / \ 2 3 / / \ 4 2 4 / 4
下面是兩個重復的子樹:
2 / 4
和
4
因此,你需要以列表的形式返回上述重復子樹的根結點。
解題思路:
這就是一道考察二叉樹遍歷的題, 遍歷的時候序列化作為 String 類型存入 Map, 若其為第二次出現即將該結點加入數組.
這里以后序遍歷為例, 需要注意葉子結點應當規(guī)定一個特殊字符作為替代 null 結點, 這里用的是 ‘#’
Java:
class Solution { public List<TreeNode> findDuplicateSubtrees(TreeNode root) { List<TreeNode> list = new ArrayList<>();//待返回數組 if (root == null) return list; Map<String, Integer> map = new HashMap<>();//哈希映射查找重覆子結點 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;//每個子樹路徑 map.put(tree, map.getOrDefault(tree, 0) + 1);//存儲每個子樹路徑 if (map.get(tree) == 2) list.add(node);//第二次出現相同路徑時存儲該結點 return tree; } }
Python:
class Solution: def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]: res = [] # 待返回數組 if not root: return res hash_map = {} # 哈希映射查找重覆子結點 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 # 每個子樹路徑 if tree in hash_map.keys(): # 存儲每個子樹路徑 hash_map[tree] += 1 else: hash_map[tree] = 1 if hash_map[tree] == 2: # 第二次出現相同路徑時存儲該結點 res.append(node) return tree
有不清楚的地方可以留言,更多的
Python學習課堂筆記也會繼續(xù)給大家更新!
當前題目:Python學習課堂筆記:尋找重復的子樹
標題路徑:http://muchs.cn/article42/piseec.html
成都網站建設公司_創(chuàng)新互聯,為您提供小程序開發(fā)、靜態(tài)網站、手機網站建設、網站收錄、企業(yè)建站、關鍵詞優(yōu)化
聲明:本網站發(fā)布的內容(圖片、視頻和文字)以用戶投稿、用戶轉載內容為主,如果涉及侵權請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網站立場,如需處理請聯系客服。電話:028-86922220;郵箱:631063699@qq.com。內容未經允許不得轉載,或轉載時需注明來源: 創(chuàng)新互聯