温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Python学习课堂笔记:寻找重复的子树

发布时间:2020-08-14 11:11:10 来源:ITPUB博客 阅读:183 作者:千锋Python唐小强 栏目:编程语言

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

题目:

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

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

示例 1:

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

下面是两个重复的子树:

 2
 /
 4

 4

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

Python学习课堂笔记:寻找重复的子树

解题思路:

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

代码:

这里以后序遍历为例, 需要注意叶子结点应当规定一个特殊字符作为替代 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学习课堂笔记也会继续给大家更新!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI