LeetCode

Appearance

297. Serialize and Deserialize Binary Tree ​

题目 ​

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

 

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []
Output: []

 

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -1000 <= Node.val <= 1000
Related Topics
  • 树
  • 深度优先搜索
  • 广度优先搜索
  • 设计
  • 字符串
  • 二叉树

  • 👍 1290
  • 👎 0

    • 思路 ​

    采用 BSF 进行节点的存取

    解法 ​

    py
    from idlelib.tree import TreeNode
from typing import Optional

# leetcode submit region begin(Prohibit modification and deletion)
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        queue = []
        res = []

        if not root:
            return ''

        queue.append(root)

        while queue:
            size = len(queue)

            while size > 0:
                size -= 1
                node = queue.pop(0)
                if not node:
                    res.append('#')
                else:
                    res.append(node.val)
                    queue.append(node.left)
                    queue.append(node.right)

        return ','.join(str(x) for x in res)


    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """

        size = len(data)

        if size == 0:
            return
        list = data.split(',')
        root = TreeNode(list[0])
        queue = [root]

        i = 1

        while queue and i < size:
            node = queue.pop(0)
            if list[i] == '#':
                node.left = None
            else:
                node.left = TreeNode(list[i])
                queue.append(node.left)

            if i + 1 == size:
                break
            elif list[i + 1] == '#':
                node.right = None
            else:
                node.right = TreeNode(list[i + 1])
                queue.append(node.right)

            i += 2

        return root

        

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度 O(N)
    • 空间复杂度 O(N)