各种遍历方式的反序列化方法

算法1

后序遍历 反序列化

Python3 代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if not root: return 'None'
        s = []
        def postorder(root):
            if not root: 
                s.append('None')
                return 
            postorder(root.left)
            postorder(root.right)
            s.append(str(root.val))
        postorder(root)
        return ' '.join(s)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        s = data.split(' ')
        n = len(s)
        pos = [n-1]
        def rpreorder(pos):
            #if pos[0]==n: return None
            if s[pos[0]]=='None':
                pos[0]-=1
                return None
            root = TreeNode(int(s[pos[0]]))
            pos[0] -= 1
            right = rpreorder(pos)
            left = rpreorder(pos)
            root.left, root.right = left, right
            return root
        return rpreorder(pos)

算法2

中序遍历 反序列化是不可以的
不妨举个例子
null 2 null 1 null 3 null
则以任意非空结点为根结点构造的二叉树，均可以序列化为上述序列

算法3

先序遍历 反序列化

Python3 代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if not root: return 'None'
        s = []
        def preorder(root):
            if not root: 
                s.append('None')
                return 
            s.append(str(root.val))
            preorder(root.left)
            preorder(root.right)

        preorder(root)
        return ' '.join(s)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        s = data.split(' ')
        n = len(s)
        pos = [0]
        def rpreorder(pos):
            #if pos[0]==n: return None
            if s[pos[0]]=='None':
                pos[0]+=1
                return None
            root = TreeNode(int(s[pos[0]]))
            pos[0] += 1
            root.left = rpreorder(pos)
            root.right = rpreorder(pos)
            return root
        return rpreorder(pos)

算法4

层次遍历 反序列化

Python3 代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        import collections
        if not root: return 'None'
        s = []
        def levelorder(root):
            if not root: 
                s.append('None')
                return
            que = collections.deque([root])
            while que:
                p = que.popleft()
                if p: 
                    s.append(str(p.val))
                    que.append(p.left)
                    que.append(p.right)
                else:
                    s.append('None')

        levelorder(root)
        return ' '.join(s)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        s = data.split(' ')
        n = len(s)

        def rpreorder():
            if s[0]=='None': return None
            root = TreeNode(int(s[0]))
            nex = [root]
            i = 1
            while nex:
                cur = nex[:]
                nex = []
                N = len(cur)
                while cur:
                    p = cur.pop(0)
                    if s[i]!='None': 
                        p.left = TreeNode(int(s[i]))
                        nex.append(p.left)
                    else: p.left = None
                    i+=1
                    if s[i]!='None': 
                        p.right = TreeNode(int(s[i]))
                        nex.append(p.right)
                    else: p.right = None
                    i+=1

            return root
        return rpreorder()