二叉树的序列化 力扣 297. 二叉树的序列化与反序列化 652. 寻找重复的子树

297. 二叉树的序列化与反序列化

解题思路：
利用前文所说，分解的思路。

序列化： 后序遍历拼接字符串。
反序列化：由于要分割字符串的逗号，额外采用一个 helper 函数来递归地分解并拼接成树。

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return 'None'

        left = self.serialize(root.left)
        right = self.serialize(root.right)

        return str(root.val) + ',' + str(left)  +','+ str(right)


    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        
        data = data.split(',')
        
        root = self.helper(deque(data))
        return root
        

    def helper(self,data):

        val=data.popleft()
        if val=='None':
            return None

        root = TreeNode(int(val))
        root.left = self.helper(data)
        root.right = self.helper(data)
        return root

652. 寻找重复的子树

解题思路：

先把树序列化为字符串。
后序遍历比较重复的字符串。

class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        """序列化整颗树的子树序列, 如果已存在这样的子树, 则输出
        """
        self.res = []
        self.counter = Counter()
        self.traverse(root)
        return self.res

    def traverse(self, root):

        if not root:
            return None
        left = self.traverse(root.left)
        right = self.traverse(root.right)
		
		#序列化字符串
        chain = str(root.val) + ',' + str(left) + ',' + str(right) 
        
		#字典记录每一个字符串
        self.counter[chain] += 1
        
        #list 中记录重复结构字符串
        if self.counter[chain] == 2:
            self.res.append(root)
        return chain