脚本宝典收集整理的这篇文章主要介绍了【LeetCode 二叉树专项】寻找重复的子树(652),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
文章目录
- 1. 题目
- 1.1 示例
- 1.2 说明
- 1.3 限制
- 2. 解法一
- 2.1 分析
- 2.2 实现
- 2.3 复杂度
给定一棵二叉树的根节点,请返回所有的重复子树。对于每一类重复子树,你只需要返回其中任意一个的根节点即可。如果两棵二叉树拥有相同的结构和节点值,则称这两棵二叉树是重复的。
示例 1 1 1 :
- 输入:
root = [1, 2, 3, 4, null, 2, 4, null, null, 4]
- 输出:
[[2, 4], [4]]
示例 2 2 2 :
- 输入:
root = [2, 1, 1]
- 输出:
[[1]]
示例 3 3 3 :
- 输入:
root = [2, 2, 2, 3, null, 3, null]
- 输出:
[[2, 3], [3]]
- 来源: 力扣(LeetCode)
- 链接: https://leetcode-cn.com/problems/find-duplicate-subtrees
- 二叉树中的节点数量在 [ 1 , 1 0 4 ] [1,textit{ }10^4] [1, 104] 之间;
-200 <= Node.val <= 200
。
想要正确解答本题,只需要知道如何给出二叉树的某种唯一性表达即可,接下来首先获得以给定二叉树的所有节点为根节点的子二叉树的表达形式,然后得到所有重复表达形式对应子树的根节点即可。
实际上,所谓给出二叉树的某种唯一表达其实就是对二叉树进行序列化,而在【LeetCode 二叉树专项】二叉树的序列化与反序列化(297)中,我们给出了基于二叉树深度优先搜索(前序遍历、后序遍历)以及广度优先搜索实现的二叉树序列化。
接下来,需要确定就是具体采用哪种方式序列化。本题采用二叉树的后序遍历对给定二叉树的所有子树进行序列化。
from json import dumps
from typing import Optional, List, Set, Dict, Union
class TreeNode:
def __init__(self, val=0, left: 'TreeNode' = None, right: 'TreeNode' = None):
self.val = val
self.left = left
self.right = right
class Solution:
def _find_duplicate_subtrees(self, root: TreeNode,
memorandum: Dict[str, int],
results: List[TreeNode]) -> Optional[List[int]]:
if not isinstance(root, TreeNode):
return
left = self._find_duplicate_subtrees(root.left, memorandum, results)
right = self._find_duplicate_subtrees(root.right, memorandum, results)
postorder = []
if left:
postorder = postorder + left
else:
postorder.append(left)
if right:
postorder = postorder + right
else:
postorder.append(right)
postorder.append(root.val)
dumped = dumps(postorder)
# if dumped in memorandum.keys() and memorandum[dumped] == 1:
if memorandum.get(dumped, 0) == 1: # The above commented if-clause is a pedantic counterpart.
results.append(root)
memorandum[dumped] = memorandum.get(dumped, 0) + 1
return postorder
def find_duplicate_subtrees(self, root: Optional[TreeNode]) -> Optional[List[TreeNode]]:
if not isinstance(root, TreeNode):
return
memorandum = dict()
results = []
self._find_duplicate_subtrees(root, memorandum, results)
print('memorandum =', memorandum)
return results
def postorder(root: TreeNode, tree: List[Union[int, None]]):
if not root:
tree.append(None)
return
postorder(root.left, tree)
postorder(root.right, tree)
tree.append(root.val)
def main():
node7 = TreeNode(4)
node6 = TreeNode(4)
node5 = TreeNode(2, left=node7)
node4 = TreeNode(4)
node3 = TreeNode(3, node5, node6)
node2 = TreeNode(2, left=node4)
node1 = TreeNode(1, node2, node3)
root = node1
sln = Solution()
for root in sln.find_duplicate_subtrees(root):
tree = []
postorder(root, tree)
print('postorder =', dumps(tree))
if __name__ == '__main__':
main()
运行上述解答的输出结果为:
memorandum = {'[null, null, 4]': 3, '[null, null, 4, null, 2]': 2, '[null, null, 4, null, 2, null, null, 4, 3]': 1, '[null, null, 4, null, 2, null, null, 4, null, 2, null, null, 4, 3, 1]': 1}
postorder = [null, null, 4]
postorder = [null, null, 4, null, 2]
实际上, LeetCode 官方通过使用 collections
模块中的 Counter
类,给出了一个如下的非常优雅的解答,其中关于 Counter 类的使用,可以参考【源码共读】Python 标准模块 collections 中 Counter 类详解。
from typing import Optional, List, Dict, Union
from collections import Counter
class TreeNode:
def __init__(self, val=0, left: 'TreeNode' = None, right: 'TreeNode' = None):
self.val = val
self.left = left
self.right = right
class Solution:
def _collect(self, node: TreeNode, duplicates: List[TreeNode], count: Counter):
if not node:
return '#'
serial = "{},{},{}".format(self._collect(node.left, duplicates, count),
self._collect(node.right, duplicates, count),
node.val)
count[serial] += 1
if count[serial] == 2:
duplicates.append(node)
return serial
def elegantly_find_duplicate_subtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
count = Counter()
duplicates = []
self._collect(root, duplicates, count)
return duplicates
def postorder(root: TreeNode, tree: List[Union[int, None]]):
if not root:
tree.append(None)
return
postorder(root.left, tree)
postorder(root.right, tree)
tree.append(root.val)
def main():
node7 = TreeNode(4)
node6 = TreeNode(4)
node5 = TreeNode(2, left=node7)
node4 = TreeNode(4)
node3 = TreeNode(3, node5, node6)
node2 = TreeNode(2, left=node4)
node1 = TreeNode(1, node2, node3)
root = node1
sln = Solution()
for root in sln.elegantly_find_duplicate_subtrees(root):
tree = []
postorder(root, tree)
print('postorder =', dumps(tree))
if __name__ == '__main__':
main()
实际上,在上述解答的 第
15
15
15 行中,如果将 return '#'
改为 return
也是正确的,但不为何此时在 LeetCode
上提交时,执行耗时和内存消耗的数据都非常差,希望看到这篇题解而且知道缘由的有缘人可以在评论区留下你的指导。
以上是脚本宝典为你收集整理的【LeetCode 二叉树专项】寻找重复的子树(652)全部内容,希望文章能够帮你解决【LeetCode 二叉树专项】寻找重复的子树(652)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。