Serialize and Deserialize BST/N-ary

一道高频题。核心思想就是用preorder先把所有values存在deque或者list里面，如果是None node的话就什么都不存。那么现在面临的问题就是如何判断root val后面的是left 还是right

这时候在builder这个recursion function里面有很重要了。用min 和max这两个boundary来判断，在min 和 curr之间的是left，反之就是right

一些感想：

刚开始用的 123 （234）（#） 这种方式，后来发现在解决判定parenthesis这里很麻烦而且会增高时间复杂度。

当这是一个Binary Search Tree时

from collections import deque
import sys
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root: TreeNode) -> str:
        """Encodes a tree to a single string.
        """
        if root == None:
            return ""
        self.vals  = []
        def dfs(node):
            if node == None:
                return
            self.vals.append(node.val)
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return " ".join(map(str,self.vals))

    def deserialize(self, data: str) -> TreeNode:
        """Decodes your encoded data to tree.
        """
        if data == "":
            return None
        vals = deque([int(val) for val in data.split(" ")])
        def builder(mmin,mmax):
            if vals and mmin < vals[0] < mmax:
                curr = vals.popleft()
                root = TreeNode(curr)
                root.left = builder(mmin,curr)
                root.right = builder(curr,mmax)
                return root
            return None
        return builder(-sys.maxsize,sys.maxsize)

当这是一个Binary Tree时

这时候，tree没有了bst的特性 left.val < curr.val < right.val 我们无法用之前的dfs 里的min & max来做判断。但我们仍然可以用deque来存储整个tree。这里面的当node为None时我们存储"#" 最后build tree时如果遇见”#“我们就直接return None。代码如下

from collections import deque

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if root == None:
            return ""
        q = []
        def dfs(node,q):
            if node == None:
                q.append("#")
                return
            q.append(node.val)
            dfs(node.left,q)
            dfs(node.right,q)
        dfs(root,q)
        return " ".join(map(str,q))

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if data =="":
            return None
        vals = deque(data.split(" "))
        def builder():
            if vals:
                val = vals.popleft()
                if val == "#":
                    return None
                node = TreeNode(int(val))
                node.left = builder()
                node.right = builder()
                return node
            return None
        return builder()

针对于n-array的树，因为不需要判断下一个是左孩子还是右孩子，我们只需要将每一个node的孩子的数量cnt记录在。

无论针对于bst还是n-array，我们都可以用deque来记录它所有孩子。

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
import collections
class Codec:
    def serialize(self, root: 'Node') -> str:
        """Encodes a tree to a single string.
        
        :type root: Node
        :rtype: str
        """
        if root == None:
            return ""
        res = str(root.val)
        arr = []
        
        children = [self.serialize(child) for child in root.children]
        arr.append(res)
        arr.append(len(children))
        arr.extend(children)
        return " ".join(map(str,arr))
	
    def deserialize(self, data: str) -> 'Node':
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: Node
        """
        self.queue = collections.deque(data.split(" "))
        def builder():
            if len(self.queue) <= 1:return None
            val = self.queue.popleft()
            cnt = self.queue.popleft()
            root = Node(int(val))
            children = []
            for _ in range(int(cnt)):
                children.append(builder())
            root.children = children
            return root
        
        return builder()
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))