本期的Python学习课堂笔记：寻找重复的子树

题目:

给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

两棵树重复是指它们具有相同的结构以及相同的结点值。

示例 1：

1/\23//\424/4

下面是两个重复的子树：

2/4

和

4

因此，你需要以列表的形式返回上述重复子树的根结点。

解题思路：

这就是一道考察二叉树遍历的题, 遍历的时候序列化作为 String 类型存入 Map, 若其为第二次出现即将该结点加入数组.

代码:

这里以后序遍历为例, 需要注意叶子结点应当规定一个特殊字符作为替代 null 结点, 这里用的是 ‘#’

Java:

classSolution{publicList<TreeNode>findDuplicateSubtrees(TreeNoderoot){List<TreeNode>list=newArrayList<>();//待返回数组if(root==null)returnlist;Map<String,Integer>map=newHashMap<>();//哈希映射查找重覆子结点traverse(root,map,list,"");returnlist;}//后序遍历privateStringtraverse(TreeNodenode,Map<String,Integer>map,List<TreeNode>list,Stringtree){if(node==null)returntree+"#";Stringleft=traverse(node.left,map,list,tree);//递归左子孩子Stringright=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);//第二次出现相同路径时存储该结点returntree;}}

Python:

classSolution:deffindDuplicateSubtrees(self,root:TreeNode)->List[TreeNode]:res=[]#待返回数组ifnotroot:returnreshash_map={}#哈希映射查找重覆子结点self.traverse(root,hash_map,res,'')returnres#后序遍历deftraverse(self,node:TreeNode,hash_map,res,tree):ifnotnode:returntree+'#'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#每个子树路径iftreeinhash_map.keys():#存储每个子树路径hash_map[tree]+=1else:hash_map[tree]=1ifhash_map[tree]==2:#第二次出现相同路径时存储该结点res.append(node)returntree


有不清楚的地方可以留言，更多的Python学习课堂笔记也会继续给大家更新！