Serialization of binary tree 297 Serialization and deserialization of binary tree 652 Find duplicate subtrees

297. Serialization and deserialization of binary trees

Their thinking ：
Make use of the above , The idea of decomposition .

serialize ： Post order traversal of concatenated strings .
Deserialization ： Because you want to split the comma of the string , Additional one helper Function to recursively decompose and splice into a tree .

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 roott

652. Look for duplicate subtrees

Their thinking ：

First serialize the tree into a string .
Post order traversal compares repeated strings .

class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        """ Serialize the sequence of subtrees of the entire tree ,  If such a subtree already exists ,  The output  """
        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)
		
		# Serialized string 
        chain = str(root.val) + ',' + str(left) + ',' + str(right) 
        
		# The dictionary records every string 
        self.counter[chain] += 1
        
        #list  Record duplicate structure string in 
        if self.counter[chain] == 2:
            self.res.append(root)
        return chain