Tree-Serialization.md

¶开始 Starting

The Serialization of Tree

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

¶题目 Question

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.

¶想法 Thinking

主要有两种方法，分别是DFS 和 BFS

¶DFS

递归三部曲：

1. 找整个递归的终止条件：递归应该在什么时候结束？
2. 找返回值：应该给上一级返回什么信息？
3. 本级递归应该做什么：在这一级递归中，应该完成什么任务？ 并且 call to the next level

¶Serialize

DFS 中，我们可以使用 PreOrder 来 遍历 所有的 Node。 递归的终止条件为 当 root不存在时候，return "#_" 如果Node 存在， 我们则提取当前 Node 的值并且加上_，然后 调用下一层，最后返回当前已经生成了的字符串

¶Deserialize

首先创建一个 queue 方便遍历 所有的Node：

queue = collections.deque()
data = data.split("_")
data = data[:-1]
for i in data:
	queue.append(i)

类似的，我们用 PreOrder 来 创建树：

如果当前 值是"#"则 return None, 如果不是则创建相应的Node 并且call 函数自己。 并当前一层 return 已经创建好了的partial tree

¶BFS

¶Serialize

对于完全二叉树，可以使用BFS 把所有 Node 给序列化。

def serialize(root):
    ans = ""
    queue = collections.deque()
    queue.append(root)
    while queue:
        cur = queue.popleft()
        if cur is None:
            ans += "#_"
        else:
            ans += str(cur.val) + "_"
        	queue.append(cur.left)
        	queue.append(cur.right)
    return ans[:-1]

与heap完全二叉树 的原理类似，我们知道：（起始于编号1）

已知一个节点的编号是 i，那么其左子节点就是 2 * i，右子节点就是 2 * i + 1，父节点就是 i / 2。

但是树不一定是完全二叉树。也就是我们需要解决这种问题：

但是注意，因为我们在以下代码使用的是 i 来做 increment， 所以它必定会遍历所有node，因为我们使用了queue 来存已经生成了的Node， 观察图，发现父子对应关系是正确的。

¶Deserialize:

def deserialze(self, data):
    if data == "#":
        return None
    nodes = data.split("_")
    if not nodes:
        return None
    root = TreeNode(int(nodes[0]))
    q = collections.deque()
    q.append(root)
    
    i = 1
    
    while i < len(nodes) -1 :
        cur = q.popleft()
        left = nodes[i]
        right = nodes[i+1]
        i += 2
        if left != "#":
            l = TreeNode(int(left))
            cur.left = l
            queue.append(l)
        if right != "#":
            r = TreeNode(int(left))
            cur.right = r
            queue.append(r)
     return root

¶算法 Algorithm

¶DFS

# 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
        """
        return self.serializeHelper(root)

    def serializeHelper(self, root):
        if not root:
            return "#_"
        res = str(root.val) + "_"
        res += self.serialize(root.left)
        res += self.serialize(root.right)
        return res

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        queue = collections.deque()
        data = data.split("_")
        data = data[:-1]
        for i in data:
            queue.append(i)
        return self.deserializeHelper(queue)
    
    def deserializeHelper(self, queue):
        cur = queue.popleft()
        if cur == "#":
            return None
        root = TreeNode(int(cur))
        root.left = self.deserializeHelper(queue)
        root.right = self.deserializeHelper(queue)
        return root
            

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

¶BFS

# 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 = collections.deque()
        queue.append(root)
        ans = ""
        while queue:
            cur = queue.popleft()
            if not cur:
                ans += "#_"
            else:
                ans += str(cur.val) + "_"
                queue.append(cur.left)
                queue.append(cur.right)     

        return ans[:-1]
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if data == "#":
            return None
        data = data.split("_")
        root = TreeNode(int(data[0]))

        queue = collections.deque()
        queue.append(root)
        # root has been added 
        i = 1

        while queue:
            cur = queue.popleft()
            lv = data[i]
            rv = data[i+1]
            i+= 2
            if lv != "#":
                l = TreeNode(int(lv))
                cur.left = l
                queue.append(l)
            if rv != "#":
                r = TreeNode(int(rv))
                cur.right = r
                queue.append(r)
        return root

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

¶

¶运行时间 Run-time

¶反思 Introspection