LeetCode 297. Serialize and Deserialize Binary Tree

题目链接：
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()