树的序列化非递归解法：前序遍历 (DFS) 和 层序遍历（BFS）

前序遍历解法
-序列化：用栈实现树的前序遍历，先访问根节点（添加“val!”），然后将指针指向左节点，一直到左节点为空（添加“#!”），弹出一个节点，将指针指向右节点。如此反复直至栈为空且当前指针指向空。
-反序列化：还是仿照树的前序遍历，先添加根节点并入栈，指针指向根节点，若下一个字符不是空结点，则添加该节点为左节点并入栈，然后将指针指向该左节点，一直到左节点为空。此时我们需要找到节点中下一个不为空的值，以此来创建右节点并入栈，注意每有一个为空的值，便要从栈中弹出一个节点（表示当前节点的右节点为空，所以需要弹出当前节点的父节点）。如此反复直至栈为空。

注：python中字符串的split方法中，若字符串中最后一个字符为分割字符（此题中为“!”），则在生成的list会以空格符“ ”结尾，所以用nodes = nodes[:-1]来去掉末尾的空格。

class Solution:
    def Serialize(self, root):
        # write code here
        if not root:    return ""
        res = ""
        stack = []
        cur = root
        while stack or cur:
            if cur:
                stack.append(cur)
                res = res + str(cur.val) + "!"
                cur = cur.left
            else:
                res = res + "#" + "!"
                cur = stack.pop()
                cur = cur.right
        print res
        return res

    def Deserialize(self, s):
        # write code here
        if len(s) == 0:    return None
        nodes = s.split("!")
        nodes = nodes[:-1]     # Remove the space " " in the last position
        root = TreeNode(int(nodes[0]))
        sub = 1
        stack = []
        stack.append(root)
        cur = root
        while stack and sub < len(nodes):
            if nodes[sub] != "#":
                cur.left = TreeNode(int(nodes[sub]))
                cur = cur.left
                stack.append(cur)
                sub += 1
            else:
                while sub < len(nodes) and nodes[sub] == "#":
                    cur = stack.pop()
                    sub += 1
                if sub < len(nodes):
                    cur.right = TreeNode(int(nodes[sub]))
                    cur = cur.right
                    stack.append(cur)
                    sub += 1
        return root

层序遍历解法
-序列化：树的层序遍历需要用队列实现，这里同样使用list实现，先将根节点入队，然后进入循环，出队一个节点（list中的第一个元素），访问该节点的值，若不为空则将其左右节点依次入队。如此反复直至队列为空。
-反序列化：同样用队列模仿层序遍历的过程，依次为每个节点建立左右节点即可。

class Solution:
    def Serialize(self, root):
        # write code here
        return self.BFS_tree(root)

    def Deserialize(self, s):
        # write code here
        if len(s) == 0:    return None
        nodes = s.split("!")
        nodes = nodes[:-1]     # Remove the space " " in the last position
        root = TreeNode(int(nodes[0]))
        Q = []
        Q.append(root)
        sub = 1
        while Q and sub < len(nodes):
            cur = Q[0]
            value = nodes[sub]
            sub += 1
            if value == "#":    cur.left = None
            else:
                cur.left = TreeNode(int(value))
                Q.append(cur.left)

            value = nodes[sub]
            sub += 1
            if value == "#":    cur.right = None
            else:
                cur.right = TreeNode(int(value))
                Q.append(cur.right)
            del Q[0]
        return root

    def BFS_tree(self, root):
        if not root:    return []
        Q = []
        res = ""
        Q.append(root)
        while Q:
            cur = Q[0]
            if cur:
                res = res + str(cur.val) + "!"
                Q.append(cur.left)
                Q.append(cur.right)
            else:
                res = res + "#" + "!"
            del Q[0]
        return res