本期的Python学习课堂笔记：寻找重复的子树
公司主营业务：成都网站设计、成都网站制作、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。创新互联是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联推出景洪免费做网站回馈大家。
题目:
给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意 一棵的根结点即可。
两棵树重复是指它们具有相同的结构以及相同的结点值。
示例 1：
1 / \ 2 3 / / \ 4 2 4 / 4
下面是两个重复的子树：
2 / 4
和
4
因此，你需要以列表的形式返回上述重复子树的根结点。
解题思路：
这就是一道考察二叉树遍历的题, 遍历的时候序列化作为 String 类型存入 Map, 若其为第二次出现即将该结点加入数组.
这里以后序遍历为例, 需要注意叶子结点应当规定一个特殊字符作为替代 null 结点, 这里用的是 ‘#’
Java:
class Solution {
public List findDuplicateSubtrees(TreeNode root) {
List list = new ArrayList<>();//待返回数组
if (root == null) return list;
Map map = new HashMap<>();//哈希映射查找重覆子结点
traverse(root, map, list, "");
return list;
}
//后序遍历
private String traverse(TreeNode node, Map map, List 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学习课堂笔记也会继续给大家更新！