题目链接:
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

将树以一种线性形式存储。

类似 JSON.stringify()parse()

思路大概就是遍历一下,然后以同样的遍历方式重新构建树。

一开始自己想的是用前序和中序遍历一下树,生成两个字符串,拼接起来,然后重新构建的时候拆分出两个数组,然后构建树。这样就不会出现什么奇怪的 “None” 代表空节点之类的。 参考这道题:LeetCode 105。不过这个解法需要树中没有重复值。还是想得有些复杂了。

参考回答:
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/discuss/924828/Easy-to-understand-Python-Solution%3A-Iterative-Preorder-and-Recursive-BuildTree

用了迭代器,代码比较整洁


class Codec:

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

        :type root: TreeNode
        :rtype: str
        """
        stack = [root]
        output = ""

        while (stack):
            node = stack.pop()
            if (node):
                output += str(node.val) + " "
                stack.append(node.right)
                stack.append(node.left)
            else:
                output += "None" + " "

        return output.strip()

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

        :type data: str
        :rtype: TreeNode
        """
        vals = iter(data.split())

        def buildTree():
            val = next(vals)
            node = None
            if val == "None":
                return None
            else:
                node = TreeNode(int(val))
                node.left = buildTree()
                node.right = buildTree()
            return node

        return buildTree()