题解 | #序列化二叉树#

层次遍历BFS

序列化和反序列化均使用队列作为辅助

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        if not root:
            return None
        q = []
        q.append(root)
        res = []
        while q:
            p = q.pop(0)
            if p == '#':
                res.append('#')
            else:
                res.append(str(p.val))
                if p.left:
                    q.append(p.left)
                else:
                    q.append('#')
                if p.right:
                    q.append(p.right)
                else:
                    q.append('#')
        for i in range(len(res)-1, -1, -1):
            if res[i] != '#':
                break
        res = ",".join(res[0:i+1])
        return res
    
    def Deserialize(self, s):
        # write code here
        if not s:
            return None
        l = s.split(',')
        p = l.pop(0)
        root = TreeNode(int(p))
        head = root
        res = []
        res.append(root)
        while l:
            root = res.pop(0)
            p = l.pop(0)
            if p != '#':
                root.left = TreeNode(int(p))
                res.append(root.left)
            if l:
                p = l.pop(0)
                if p != '#':
                    root.right = TreeNode(int(p))
                    res.append(root.right)
        return head