首页 > itarticle > l297. serialize and deserialize binary tree

l297. serialize and deserialize binary tree

admin 11月 13, 2020 0

题目描述

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.

For example, you may serialize the following tree

as “[1,2,3,null,null,4,5]”, just the same as how LeetCode OJ serializes a binary tree.
You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

解题思路

本题目完全使用Discuss https://discuss.leetcode.com/topic/28041/recursive-preorder-python-and-c-o-n

Python实现


import unittest


class (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
        """

        def doit(node):
            if node:
                vals.append(str(node.val))
                doit(node.left)
                doit(node.right)
            else:
                vals.append('#')

        vals = []
        doit(root)
        n = len(vals) - 1
        while vals[n] == '#':
            n -= 1
        return ','.join(vals[0:n + 1])

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

        :type data: str
        :rtype: TreeNode
        """

        def doit():
            try:
                val = next(vals)
                if val == '#':
                    return None
                node = TreeNode(int(val))
                node.left = doit()
                node.right = doit()
                return node
            except StopIteration:
                pass

        vals = iter(data.split(','))
        return doit()


class Test(unittest.TestCase):
    s = Codec()

    def test_case1(self):
        data = "1,2,3,#,#,4,5"
        root = self.s.deserialize(data)
        ret = self.s.serialize(root)
        self.assertEquals(ret, data)

    def test_case2(self):
        data = "1,2,3,#,#,4"
        root = self.s.deserialize(data)
        ret = self.s.serialize(root)
        self.assertEquals(ret, data)

    def test_case3(self):
        data = "5,2,3,#,#,2,4,3,1"
        ret = self.s.serialize(self.s.deserialize(data))
        self.assertEquals(ret, data)