652. 寻找重复的子树

Difficulty
Medium
Tags
二叉树
URL
https://leetcode-cn.com/problems/find-duplicate-subtrees/
Star
给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
两棵树重复是指它们具有相同的结构以及相同的结点值。
示例 1：
下面是两个重复的子树：
      2
     /
    4
和
    4
因此，你需要以列表的形式返回上述重复子树的根结点。

分析

借助一个外部数据结构，让每个节点把自己子树的序列化结果存进去，这样，对于每个节点，就可以知道有没有其他节点的子树和自己重复了

法1

思路
遍历二叉树，遍历的时候将每个节点的子树序列化存到字典，同时判断该子树序列化在字典中有没有，如果有，存到result中
题解
# 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.dict = {}   # 存放所有节点子树序列化字符串的字典
        self.result = [] # 存放最后结果的列表
    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
        if root is None:
            return self.result
        # 保存树的所有节点的子树
        self.traverse(node=root)
        return self.result

    def traverse(self, node):
        str_ = ""
        if node is None:
            return "#"

				# 注意， 此题不能采用中序遍历，
				# 因为中序遍历结果不唯一，可能有不同子树中序遍历的结果相同
        str_ = str(node.val) + ","  + self.traverse(node.left) + "," + self.traverse(node.right)
        if str_ in self.dict:
            # 如果原先就有一次，就存到结果中，否则不存到结果的
            if self.dict[str_] == 1: 
                self.result.append(node)
            self.dict[str_] += 1
        else:
            self.dict[str_] = 1
        return str_