Iterative BFS, Python, Beats 98%


  • 0
    K
    class Codec:
    
        def serialize(self, root):
            """Encodes a tree to a single string.
            
            :type root: TreeNode
            :rtype: str
            """
            res = []
            if not root: 
                return res
            q = collections.deque()
            q.append(root)
            while q:
                node = q.popleft()
                if not node:
                    res += ['#']
                   
                else:
                    res += [node.val]
                    q.append(node.left)
                    q.append(node.right)
            
            while res[-1] == '#':   # remove trailing '#'
                res.pop()
            return res
    
        def deserialize(self, data):
            """Decodes your encoded data to tree.
            
            :type data: str
            :rtype: TreeNode
            """
            if not data: return None
            q = collections.deque()
            data.reverse()
            root = TreeNode(data.pop())
            q.append(root)
            while q and data:
                cur = q.popleft()
                tem1 = data.pop()
                cur.left = TreeNode(tem1) if tem1 != '#' else None
                if cur.left:
                    q.append(cur.left)
                
                if data:    # if data is empty , do not create the right leaf 
                    tem2 = data.pop()
                    cur.right = TreeNode(tem2) if tem2 != '#' else None
                    if cur.right:
                        q.append(cur.right)
            return root

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.