297 Serialize and Deserialize Binary Tree

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

solution

• bfs: decode函数就类似构造树的题目

class Codec:
    def serialize(self, root):
        if not root:  # 否则会输出一个#
            return ''

        data = []
        queue = collections.deque([root])
        while queue:
            node = queue.popleft()
            if node:
                data.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                data.append('#')
        return ','.join(data)

    def deserialize(self, data):
        if not data:
            return

        data = data.split(',')
        root = TreeNode(data[0])
        queue = collections.deque([root])
        # when you pop a node, its children will be at i and i+1
        for i in range(1, len(data), 2):
            node = queue.popleft()
            if data[i] != '#':
                node.left = TreeNode(data[i])
                queue.append(node.left)
            if data[i + 1] != '#':
                node.right = TreeNode(data[i + 1])
                queue.append(node.right)
        return root

时间复杂度：O(n) 空间复杂度：O(n)

• dfs

follow up-序列化和压缩类题目

449. Serialize and Deserialize BST

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        """Encodes a tree to a single string."""
        if not root:
            return ''
        
        queue = collections.deque([root])
        res = []
        while queue:
            node = queue.popleft()
            if node:
                res.append(str(node.val))
                queue.extend([node.left, node.right])
            else:
                res.append('*')
        return ','.join(res)        

    def deserialize(self, data: str) -> Optional[TreeNode]:
        """Decodes your encoded data to tree."""
        if not data:
            return
        
        tree = deque(data.split(','))
        root = TreeNode(int(tree.popleft()))
        queue = collections.deque([root])
        while queue:
            node = queue.popleft()
            left = tree.popleft()
            right = tree.popleft()
            if left != '*':
                node.left = TreeNode(int(left))
                queue.append(node.left)
            if right != '*':
                node.right = TreeNode(int(right))
                queue.append(node.right)
        return root

*271. Encode and Decode Strings

# 长度标识

*288. Unique Word Abbreviation

320. Generalized Abbreviation

535. Encode and Decode TinyURL

394 Decode String

*536. Construct Binary Tree from String

652. Find Duplicate Subtrees

class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        counter = collections.defaultdict(int)
        res = []

        def dfs(root):
            if not root:
                return ''
            
            encoded = str(root.val) + '#' + dfs(root.left) + '#' + dfs(root.right)
            counter[encoded] += 1

            if counter[encoded] == 2:
                res.append(root)
            return encoded        
        
        dfs(root)
        return res

*428. Serialize and Deserialize N-ary Tree

class Codec:
    def serialize(self, root):
        if root is None:
            return []

        queue = [root]
        result = [root.val]  # add root value

        while queue:
            node = queue.pop(0)
            if node is None:
                continue

            for child in node.children:
                queue.append(child)
            result.append(len(node.children))  # add count of children, 先记录一个长度
            result.extend([child.val for child in node.children])  # add children values

        return result

    def deserialize(self, data):
        if not data:
            return None

        root = Node(data[0])  # get root from first index
        data = data[1:]  # remove root from data 
        queue = [root]

        while queue:
            node = queue.pop(0)
            if node is None:
                continue

            for _ in range(data.pop(0)):  # check children count
                child = Node(data.pop(0))  # get child value
                node.children.append(child)
                queue.append(child)
        
        return root