leetcode-652 寻找重复的子树

  • English:

leetcode-652 寻找重复的子树

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

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

示例 1:

1
2
3
4
5
6
7
    1
/ \
2 3
/ / \
4 2 4
/
4

下面是两个重复的子树:

1
2
3
  2
/
4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
    4
```
因此,你需要以列表的形式返回上述重复子树的根结点。

思路:
1. 先了解子树结构,通过左子树和右子树遍历了解的以x为根节点的子树形式
2. 通过备忘录保存已出现的子树形式,来判断是否重复

```python3
import collections
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def __init__(self):
self.memo = collections.defaultdict(int)
self.res = []

def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
self.traverse(root)
return self.res

def traverse(self, root):
if not root:
return '#'

left = str(self.traverse(root.left))
right = str(self.traverse(root.right))

subtree = left + ',' + right + ',' + str(root.val)

freq = self.memo[subtree]
if freq == 1:
self.res.append(root)
self.memo[subtree] +=1
return subtree

-------The end of this article  Thank you for your reading-------
  • 本文作者: Eree
  • 本文链接: https://ereebay.me/posts/43177/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!